問題タブ [big-o]

一般に、複雑な関数を分析する場合、定義する変数は 1 つまたは 2 つだけではないため、"n" を定義するのが難しいのではないかと思います。

循環的複雑度の分析ツールはありますが、時間 (および/または空間) 複雑度の分析ツールはありますか? もしそうなら、それはどれですか？そうでないなら、なぜですか？それは実行不可能ですか？不可能？誰かがそれに慣れていないだけですか？

理想的には、アプリケーションの全体的な複雑さのようなもの (さまざまな可能な "n" を定義する) と、アプリ内の各メソッドのようなものがあるでしょう。

編集：停止問題のために正確な解決策は不可能のようですが、ある種のヒューリスティックな近似は可能ですか? 実用的な目的では、優れたプロファイラーがはるかに有用な情報を提供することを認識していますが、それは興味深い問題のようです。

また、プログラムの特定のサブセットを計算するものはどうですか?

タイトル付きの配列を使用しています。各タイトル インデックスは、そのタイトルの html を含むデータベース内の ID に対応します。

タイトルの 1 つを含む文字列があるとします。

文字列「タイトル」を使用して対応する ID を取得するには、次のようにします。

私が使用できる別の方法は、titles の正反対である titles 配列と共に連想配列を作成することです。つまり、文字列をインデックスとして使用し、数値を返します。

次に、次の方法で ID にアクセスできます。

CPU、メモリなどを考慮すると、何が最も効果的でしょうか?

また、私の論理がすべて間違っている場合はお知らせください。

ありがとうウィレム

Aho、Hopcroft、Ullman の「データ構造とアルゴリズム」を読んでいて、演習 1.12 B と混同しています。

この Pascal 手続きの計算量 (Big O 表記で表される) はどれか?

手伝っていただけませんか？

ありがとう！

私はデータベースにかなり慣れていないので、これがばかげた質問であれば許してください。

現代のデータベースでは、インデックスを使用して行にアクセスすると、O(1) の複雑さになると思います。しかし、別の列を選択するクエリを実行すると、O(1) または O(n) になりますか? データベースはすべての行を反復処理する必要がありますか?それとも、列ごとに並べ替えられたリストを作成しますか?

私の質問は、「BigOのわかりやすい英語の説明」という投稿から生じています。対数の複雑さの正確な意味はわかりません。時間と操作の数の間で回帰を行い、Xの二乗値を計算して、その複雑さを判断できることを私は知っています。しかし、紙の上で素早く判断する方法を知りたいです。

対数の複雑さをどのように判断しますか？良いベンチマークはありますか？

大学でアルゴリズムのコストの計算についてすべて学びましたが、それはずっと前のことで、すべて忘れていました。主題全体を網羅するウォークスルーはありますか? 私が今覚えている以上のことがあったように感じます。コアスキルの一部をリフレッシュしたい。

私が読んだ本によると、このコードはO（（n ^ 3）/ 4）であるはずです。しかし、明らかにそうではありません。ネストされたループのBig-Oを見つけるために、境界を乗算することになっていますか？したがって、これはnum * n*nまたはn/4 * n*nである必要があります。

動的配列に関するウィキペディアの記事によると、配列の最後での挿入/削除はO（1）であり、中央からの挿入/削除はO（n）です。なぜそれが正確なのですか？

また、5つの要素を持つ動的配列があり、位置6に新しい要素を挿入した場合、操作はO（n）ですが、関数を使用して配列の最後に追加すると、O（1）になります。どちらの場合も配列のサイズを変更する必要がないと仮定すると、これは同じ操作ではありませんか？または、動的配列に追加すると、位置6以外の場所に新しい要素が実際に挿入されますか？

ありがとう！

編集：私の主な混乱は、配列の最後に挿入することと、配列の最後に相当する特定の位置に挿入することの違いだと思います。

配列の最後のメモリアドレスへのポインタが手元にあると思います。そのため、追加操作が高速です。逆に、正確な位置を指定すると（配列の最後であっても）、その位置に挿入することは前述のメモリアドレスを使用することと同じであることがわからないため、配列全体をトラバースする必要があります。