問題タブ [time-complexity]

JavaScript 配列に値が含まれているかどうかを確認する最も簡潔で効率的な方法は何ですか?

これは私が知っている唯一の方法です：

これを達成するためのより良い、より簡潔な方法はありますか?

時間複雑度とは何ですか? なんで？

^{ある 32 ビット符号なし整数 N に対して、長さが最大 ​​2 32}の 32 ビット符号なし整数配列が与えられ、配列内のエントリの半分以上が N に等しいというプロパティがあります。各数値を見て N を見つけます。配列内で 1 回だけ使用し、最大 2 kB のメモリを使用します。

ソリューションは決定論的で、N を見つけることが保証されている必要があります。

new、mallocなどを使用した動的メモリ割り当ての時間計算量は? 私はメモリ アロケータがどのように実装されているかについてほとんど知りませんが、その答えは実装に依存するということだと思います。したがって、より一般的なケース/実装のいくつかについて回答してください。

編集:最悪の場合、ヒープ割り当てが無制限であると聞いたのを漠然と覚えていますが、平均/典型的なケースに本当に興味があります。

Big-O 表記法は理解できますが、多くの関数で計算する方法がわかりません。特に、単純なバージョンのフィボナッチ数列の計算上の複雑さを理解しようとしています。

フィボナッチ数列の計算上の複雑さとはどのように計算されますか?

さて、私はプログラムを非常に遅くしているこのビットのコードを持っています。これは線形複雑ですが、何度も呼び出されてプログラムを二次複雑にするためです。可能であれば、計算の複雑さを減らしたいと思いますが、それ以外の場合は、できる限り最適化します。これまでのところ、次のように削減しました。

私が見逃したものを見た人はいますか？ありがとう！

編集: 言い忘れました: n は常に素数です。

EDIT 2:これが私の新しい改良されたプログラムです(すべての貢献に感謝します!):

EDIT 3:実際のコンテキストでテストすると、はるかに高速です! この質問は解決されたように見えますが、多くの有用な回答があります。また、上記の最適化と同様に、Python 辞書を使用して関数をメモしました...

ときどき、途中に何かが入った奇妙な Θ 記号の Θ(n) を見たり、O(n) だけを見たりすることがあります。誰もこの記号を入力する方法を知らないので、単にタイプするのが面倒なのでしょうか、それとも別の意味でしょうか?

別の既知のアルゴリズムよりも時間の複雑さが悪いが、すべての実際の状況でより良い選択である広く使用されているアルゴリズムはありますか (複雑さは劣りますが、それ以外の場合は優れています)?

受け入れられる答えは、次のような形式です。

それに応じてと時間の複雑さを持つアルゴリズムがありますがA、定数が非常に大きいため、宇宙内の原子の数よりも少ない入力に対しては 利点がありません。BO(N**2)O(N)BA

回答のハイライトの例:

• シンプレックス アルゴリズム -- 最悪の場合は指数時間 --対凸最適化問題の既知の多項式時間アルゴリズム。

• 中央値アルゴリズムの単純な中央値 -- 最悪の場合の O(N**2)対既知の O(N) アルゴリズム。

• バックトラッキング正規表現エンジン -- 最悪の場合の指数対O(N) Thompson NFA ベースのエンジン。

これらの例はすべて、最悪のシナリオと平均的なシナリオを比較したものです。

最悪のケースと平均的なケースのシナリオの違いに依存しない例はありますか?

関連している：

• 「悪いほうがいい」の台頭。(この質問の目的のために、「Worse is Better」というフレーズは、記事よりも狭い(つまり、アルゴリズムの時間の複雑さ) 意味で使用されています)

• Python の設計哲学:

  ABC グループは完璧を目指して努力しました。たとえば、漸近的に大きなコレクションに最適であることが証明されたツリーベースのデータ構造アルゴリズムを使用しました (ただし、小さなコレクションにはあまり適していませんでした)。

  この例は、これらの大規模なコレクションを格納できるコンピューターがない場合の答えです (つまり、この場合、大規模では十分な大きさではありません)。

• 正方行列乗算のCoppersmith–Winograd アルゴリズムは良い例です (これは最速 (2008 年) ですが、悪いアルゴリズムより劣っています)。他のもの？ ウィキペディアの記事から: 「現在のハードウェアでは処理できないほど大きな行列に対してのみ利点があるため (Robinson 2005)、実際には使用されていません。」

正式な定義はできるだけ少なく、簡単な数学を好む.

次のコードの時間計算量を計算する必要があります。

O(n^2)ですか？