最初に N 個の要素を処理し、次に N 個の半分、次に N 個の 4 分の 1 というように処理するアルゴリズムがあるとします。O(n log n) ではなく、O(fibonacci(n)) のようなアルゴリズムの実行時間を特徴付けることに意味があるでしょうか? フィボナッチ関数を使用したいのは、より具体的に見えるからです。一方で、物議をかもしているように聞こえます。
編集：
申し訳ありませんが、それ自体が興味深い質問のようですが、回答により、まったく別のものが必要であることがわかりました:)
4 に答える
2
N + 1/2 N + 1/4 N + 1/8 N + .... 約 2 N :) したがって、1 つのアイテムの処理が O(1) の場合、複雑さは依然として O(N) です。
于 2013-03-31T13:17:31.523 に答える
0
いいえ、そうではありません。コンピューター サイエンスにおけるBig O 表記 の全体的なポイントは、アルゴリズムのコストの漸近的な制限を提供することです。したがって、たとえば、ほぼすべての の使用で暗示される隠し定数を無視しますO(x)。同様に、分析でモデル化されたすべての操作は、まれな特定の状況 (たとえば、一部の暗号計算で使用される任意精度の演算) を除いて、等しいコストであると想定しています。目標は正確さではなく、よく理解された共通の理解です。
于 2013-03-31T14:05:16.270 に答える