O(1) の追加メモリのみを使用して、C++ 文字列内の単語をその場で逆にする宿題に問題があります。O(1) 追加メモリの意味に混乱しています。O(1) が一般的に何を意味するかを理解しています。入力がどれほど大きくても、計算時間は一定であるため、単語を逆に追跡するメモリを 1 つだけ追加する必要があると思います。助言がありますか？
質問する
1684 次
1 に答える
2
O(1) 追加メモリとは、「多くても一定の追加メモリを使用する」ことを意味します。たとえば、文字列のコピーを保存することはできません。これは O(n) のスペースが必要になるためintですchar。
より一般的には、「O(1)」や「O(n)」などのステートメントは、必ずしもランタイムを指すとは限りません。Big-O 記法は、関数を記述する方法です。アルゴリズムを O(n) にすることはできませんが、その実行時間を O(n) にすることはできます。同様に、アルゴリズムのスペース使用量は、O(1)、O(n)、O(2 n ) などになります。
お役に立てれば！
于 2013-10-07T01:51:35.113 に答える