コーディングテスト対策で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"
「入力データがどんなに多くても、計算は１回で済む様にしてね」
ということ。
アルゴリズムのO記法で書くと"O(1)"。
結論
"You must implement a solution with a linear runtime complexity and use only constant extra space."
→「データ量が増えた分だけ計算量が増えるO(n)対策を必ず行ってください。そしてそれは、データ量に関わらず計算が常に一回になるO(1)でなければなりません」
参考記事