問題タブ [time-complexity]

Haskellでこのコードカタをいじっていたところ、このトピックの質問に出くわしました。

インデックスが単一の数値である配列の中点を見つけるのは簡単ですが、Haskellの配列インデックスは、たとえば、カードがインスタンスであるタプル（Int、Word、Card）を含む、Ix型クラスの任意のインスタンスにすることができます。 Ixですが、Numではありません。

配列の中点を取得する1つの方法は、その長さを照会し、インデックスのリストを照会し、そのリストの半分を削除することですが、これにはO（n）時間が必要です。

定数時間でインデックスを作成する方法を知っている人はいますか？Ix範囲は整数範囲でバイジェクトすることになっているので、1つあるべきだと思います。

私は先週学校でフィボナッチ数列のn：番目の数を計算する関数を実装する任務を負いました。「サブ割り当て」は、関数O（n）の時間計算量を与えるために、累積（正しい変換ではない可能性があります）を使用して実装することでした。関数を作成しようとするまで（Int-> Integer）、これはすべて正常に機能しました。少し実験してみると、非常に大きな数の場合、時間計算量はO（n ^ 2）に近いことがわかりました。これは整数の実装が原因であるに違いないことに気づきました。これは、それがどのように機能するかについて少し興味をそそられます。私はいくつかのグーグル検索をしましたが、役に立つと思われるものは何も見つかりませんでした。それで、説明またはそれを完全に説明するリンクのいずれかを得ることを期待して皆さんに頼っています。

私のコード：

私はすべての答えに感謝しています

ヴィクトル

2つのアルゴリズムはΘ（n ^ 2）の同じシータ特性を持っていますか？

そうでない場合、これはこの特性がΘ（n ^ 3）ではないことを意味しますか？

関数 A が O(n^2) 時間で実行される n^c 個の関数 B を呼び出す場合、関数 A の時間計算量はどれくらいですか? 多項式（n ^ c）だけでなく、cが大きくなっただけですか？

複雑度クラスを見つけるように求められましたが、Big-Omega 表記と Big-O 表記のどちらを使用すればよいかわかりません。しかし、定数を削除すると、それは O(N/2) であり、次に O(N) であると想定しています。

これについては、Nをドロップした後、O（N）* O（N + 1）-> O（N ^ 2 + N）、次にO（N ^ 2）だと思いますか？

最初のものでは、n、lognなどの置換方法を使用します。すべてが私に間違った答えを与えました。
漸化式：根が定数になるので、適用できるかどうかわかりません。

誰か助けてもらえますか？

これは、G。MichaelScneiderとJudithL.Gerstingによる教科書InvitationtoComputerScienceからの直接の引用です。

セクション3.4.2の最後で、リストをソートしてからバイナリ検索を使用するのではなく、ソートされていないリストで順次検索を使用することのトレードオフについて説明しました。リストのサイズがn=100,000の場合、比較の数の点で2番目の選択肢が優れている前に、最悪の場合の検索を何回実行する必要がありますか？

質問が何を求めているのか、私にはよくわかりません。

シーケンシャル検索は次数（n）で、バイナリは次数（lgn）であり、いずれの場合もlgnは常にn未満になります。そしてこの場合、nはすでに与えられているので、私は何を見つけることになっています。

これは私の宿題の1つですが、どうしたらよいかわかりません。誰かが私のために平易な英語で質問を説明できますか？

Euclid の最大公約数アルゴリズムの時間計算量を判断するのに苦労しています。疑似コードでのこのアルゴリズムは次のとおりです。

aとbに依存しているようです。私の考えでは、時間の計算量は O(a % b) です。あれは正しいですか？それを書くためのより良い方法はありますか？

アルゴリズムが何回反復するかを確認するためにカウンターを保持することによってそれを行うことができますか、それとも期間を記録する必要がありますか？

私は Big-O について独学をしています。次の表記法の例をアルゴリズムに与える方法を理解しています。

オン）：

O(N^2):

O(N^3):

私はよく理解していないこれらの表記法に出くわしました。アルゴリズムの観点からこれらの例をどのように挙げればよいでしょうか?

たぶん、次のように表現する必要があります: に比例して実行時間がかかるアルゴリズムを書きます:

1. O((n^3)/4)
2. ログ n^3
3. O((log^2)n)+O(n)
4. 4^n
5. n^3/2