search
LoginSignup
0

posted at

[LeetCode]コーディングテスト対策:"a linear runtime complexity"と"use only constant extra space"の意味

コーディングテスト対策でLeetCodeの問題を初めて解いているのですが、問題文の英語表現に馴染みがなくそれなりに苦戦しています。

一度調べただけでは忘れてしまうので、備忘録として残しておきます。

"You must implement a solution with a linear runtime complexity and use only constant extra space."

DeepL翻訳さん
「あなたは、線形実行時複雑さと一定の余分なスペースだけを使用するソリューションを実装する必要があります。」

なるほど、わけわからん。私は仕事で通訳をしていますが、自力で読んでも意味がわかりませんでした。これは、知識として知らなければ意味が理解できないパターンです。

(出典:LeetCodeの「Top Interview Questions」>「136. Single Number」)

"a linear runtime complexity"

コードを実行した際のの実行(計算)時間が、入力されたデータサイズに比例すること。

例えば、配列のループ処理等です。配列の要素が多ければ多いほど、ループを終了するのに時間がかかります。

アルゴリズムのO記法で書くと"O(n)"。

"use only constant extra space"

「入力データがどんなに多くても、計算は1回で済む様にしてね」

ということ。

アルゴリズムのO記法で書くと"O(1)"。

結論

"You must implement a solution with a linear runtime complexity and use only constant extra space."
→「データ量が増えた分だけ計算量が増えるO(n)対策を必ず行ってください。そしてそれは、データ量に関わらず計算が常に一回になるO(1)でなければなりません」

参考記事

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0