38

私が行っている話を解決するために（最悪の場合）指数関数的な時間計算量を要する問題の直感的で現実的な例を探しています。

これが私が思いついた他の時間計算量の例です（それらの多くはこのSOの質問から取られました）：

  • O（1）-数値が奇数か偶数かを判断する
  • O（log N）-辞書で単語を検索する（二分探索を使用）
  • O（N）-本を読む
  • O（N log N）-トランプのデッキを並べ替える（マージソートを使用）
  • O（N ^ 2）-トロリーのショッピングリストにすべてがあるかどうかを確認します
  • O（無限大）-頭に着地するまでコインを投げる

何か案は？

4

5 に答える 5

35
  • O（10 ^ N）：考えられるすべての組み合わせをテストしてパスワードを破ろうとしています（長さNの数値パスワードを想定）

psなぜあなたの最後の例は複雑さO（無限大）ですか？それは線形探索ですO（N）..世界には70億人未満の人々がいます。

于 2011-08-14T07:55:15.607 に答える
4

ピザレストランには、いくつかのトッピングから選択できます

  • ペパロニ
  • 唐辛子
  • パイナップル（試してみるまでノックしないでください！）

顧客は、ピザにトッピングの任意の組み合わせを選択することも、まったく選択しないこともできます。次に、トッピングの可能なすべての一意の組み合わせを見つけるアルゴリズムを考えてみましょう。これは、時間計算量O（2 ^ n）の指数アルゴリズムです。

メニューに新しいトッピングを追加すると、可能な組み合わせが（指数関数的に）どのように成長するかを確認してください。

0 toppings: 1 combination (no toppings at all)
1 toppings: 2 combinations (none, a)
2 toppings: 4 combinations (none, a, b, ab)
3 toppings: 8 combinations (none, a, b, c, ab, ac, bc, abc)
...
...
10 toppings: 1,024 combinations
20 toppings: 1,048,576 combinations

たった20種類のトッピングで、100万以上の組み合わせが可能です！

于 2020-06-14T11:34:06.537 に答える
1

ブルートフォースでナイーブなn-queens問題の解決策。

他の人に奪われることなく、n個のクイーンを*nボードに配置する必要があります。

while there are untried configs, go to next solution and test it

すべての女王が特定の行にあると仮定すると、女王が配置される可能性はn個あり、他の（n-1）個の女王はn個あります（重複する行はチェックされないため）。

したがって、O（n ^ n）の複雑さがあります

于 2011-08-14T08:01:10.893 に答える
1

巡回セールスマン問題の力ずくの解はO（n！）であり、これはおよそO（N ^ N）です。

于 2011-08-14T07:54:48.863 に答える
1

それらの合計が指定された値Xになるように、セット内の整数のサブセットを見つけるのはどうですか？

これは複雑さがあると思いますO（2 ^（n / 2））

于 2017-05-20T09:20:31.603 に答える