問題タブ [space-complexity]

1 から 100 までの数字の配列があります。2 つの数字がありません。O(n) 時間と O(1) 空間を使用してこれらの 2 つの数値を見つけます。配列内のこれらの数値はソートされていないことに注意してください。例 : 配列 [4,欠落, 1,欠落, 2] があるとします。ご覧のとおり、欠落は 3 と 5 です。1 から 5 までの数字と 2 つの数字の配列が欠落していると仮定します。実際には [4, 1, 2] で、3 と 5 はありません。

だから、私はこれを解決する方法がわかりません。あなたの誰かが私を助けることができますか？私のプログラミング言語は c++ です。ここに配列があります：

{24, 44, 19, 92, 1, 18, 28, 50, 88, 5, 52, 11, 76, 39, 82, 85, 65, 93, 98, 4, 72, 94, 45, 59, 48 , 46, 47, 67, 87, 99, 14, 70, 80, 25, 20, 22, 21, 41, 77, 73, 2, 13, 36, 6, 27, 81, 29, 62, 8, 35 , 32, 49, 10, 100, 90, 78, 30, 34, 51, 9, 43, 58, 26, 33, 64, 15, 17, 57, 12, 56, 61, 79, 75, 97, 84 , 42, 55, 83, 91, 86, 38, 89, 96, 74, 23, 7, 68, 60, 16, 66, 69, 53, 3, 71, 37, 63, 54, 95}

コード内のコメントは、プログラムの時間の複雑さを増加させますか?

関数内でコメントされているコードがある多くの実行中のアプリケーションがあります。

これらのコメント付きコードは関数内で 500 行あり、実際のコードはわずか 10 行です。これは時間の複雑さに影響しますか?

これらのコメントはアプリケーションのサイズを大きくしますが、コメントされたコードを含むそれぞれの関数が呼び出されるときに、アプリケーションの効率に影響しますか?

次の関数の時間と空間の複雑さを計算する方法。試してみましたが、再帰関数呼び出しのために混乱しています。

以下のアルゴリズムの漸近的な空間と時間の複雑さを、(定数の 12 桁とは異なる) 任意の長さの初期入力数に対して適切な条件で提供するように求められます。

このアルゴリズムは 12 桁の数値に適用され、各桁は配列に格納されますd[](したがってd[1]、 、d[2]、...がありますd[12]) 。

時間の複雑さはわかりましたO(n)が、空間の複雑さをどのように判断すればよいですか?

インタビューでこう聞かれましたが、この方法の複雑さは何ですか??

O(1) の追加メモリのみを使用して、C++ 文字列内の単語をその場で逆にする宿題に問題があります。O(1) 追加メモリの意味に混乱しています。O(1) が一般的に何を意味するかを理解しています。入力がどれほど大きくても、計算時間は一定であるため、単語を逆に追跡するメモリを 1 つだけ追加する必要があると思います。助言がありますか？

n配列内の正の実数が与えられたとき、この集合の中に、その和が の範囲にあるような 3 つの要素が存在する(1, 2)かどうかを調べます。線形時間と一定空間でそれを行います。

• 配列は順序付けされていません。
• 数値は正です
• 数字は実数です

どんな助けでも大歓迎です。ありがとう。