問題タブ [space-complexity]

単一に接続されたリンクリストがあり、ブロックサイズが指定されています。たとえば、リンクリストが1->2->3->4->5->6->7->8-NULLで、ブロックサイズが4最初の要素を逆にして4から、次の4つの要素を逆にした場合、問題の出力は次のようになります。4->3->2->1->8->7->6->5-NULL

リンクリストをサイズのセグメントに分割して4から逆にすることを考えていました。しかし、そうすれば、まったく望ましくない多くの余分なノードを使用せざるを得なくなります。スペースの複雑さは最小限に抑える必要があります。

余分なノードの使用を最小限に抑えるより良いソリューションを誰かが提供できれば、非常に高く評価されます。

チューリングマシンの時間計算量と空間計算量の定義は同じであり、それらを区別することはできないと思います。

私を助けてください。ありがとう。

O( n )の時間複雑度を持つアルゴリズムは、 O( n ² ) またはそれ以上の空間複雑度を持つことができますか?

重複の可能性:
Big O の平易な英語の説明

私は、自分が書いたアルゴリズムの Big-O 時間と空間の複雑さを計算するのに常に苦労してきました。

アルゴリズムのスペースの複雑さについてもっと勉強するための良いリソースを教えてください。

編集:ここに投稿する前に、チュートリアルを検索しました。残念ながら、すべてのチュートリアルは実行時の複雑さに焦点を当てており、スペースの複雑さについては数行しか書いていません。

スタートアップでこの質問をされた

Bing Mapsのようなマップを設計するように求められた場合、スペースの複雑さをどのように見積もりますか？

地図について考えられる唯一の答えは、スペースは一定でしたが、正しい方向に進んだかどうかはよくわかりませんでした。

そのような質問にどのようにアプローチするのですか？

次のC関数について考えてみます。

上記の関数のスペースの複雑さは次のとおりです。

（a）O（1）（b）O（n）（c）O（n！）（d）O（n ^ n）

私が行ったことは、上記のコードの漸化式を計算することですが、それでもその漸化式を解決することはできません。これは在宅勤務関連のサイトではないことを私は知っています。しかし、どんな助けもいただければ幸いです。

これが私の再発です。

T（n）= T（n-1）+ T（n-2）+ T（n-3）+ T（n-4）+ ........ + T（1）+ S

ここで、Sは定数です。

2つの行列を乗算する場合、結果を格納するために3番目の行列を割り当てる必要があります。アルゴリズムのメモリ消費量を計算するときに、この割り当てを考慮する必要がありますか？

クイックソートは、O（log n）スタックスペースを必要とするという事実にもかかわらず、インサイチュ（インプレース）アルゴリズムとして説明されることがよくあります。つまり、insituは「必要な追加スペースがO（n）未満」を意味するのでしょうか、それともスタックスペースは一般にスペースの複雑さとしてカウントされないのでしょうか（しかし、なぜそうなるのでしょうか）、またはQuicksortは実際にはinsituアルゴリズムではありませんか？

引数の 1 つだけに関して、この関数の厳密にバインドされた時間の複雑さを見つけようとしています。私はそれが O(p^2) (またはかなり大きなシータ) だと思っていましたが、もうわかりません。

あなたが与えられた場合：

• 一定量のデータ
• データサイズの半分のサイズのメモリ
• データの一部がソートされます
• ソートされたデータのサイズがわかりません。

どのソートアルゴリズムを選択しますか? 挿入とクイックソートの間で議論しています。挿入ソートの最良のケースは O(n) ですが、最悪のケースは O(n ² ) であることはわかっています。また、メモリが限られているという事実を考慮して、データを2つの部分に分割し、それぞれでクイックソートを実行してから、すべてをマージします. データを分割するのに O(n) 時間、データをマージするのに O(n) 時間、クイックソートを使用してデータを並べ替えるのに O(n log n) 時間がかかり、正味実行時間は O(n log n) です。

これを改善する方法について何か提案はありますか？