0

対数複雑度の場合、対数の底を決定する要因は何ですか? SOに関する関連する質問を読みました（このように）。二分探索、二分木走査などの場合、データは毎回2つに分割されるため、ログのベースは2です。しかし、私はまだ理解できません/他のベースの例を考えることはできません. 対数複雑度の他の底の例は何ですか?

4

2 に答える 2

2

ある基数から別の基数に変更するには、定数を掛ける必要がありますが、複雑さは変わらないため、基数の選択は重要ではありません。O(ログ(N)) = O(ログ(N))。

たとえば、あるアルゴリズムが、N が問題のパラメータである場合に、大きな N の極限でK = 1.23 log 2 (N) に近づくステップ数を含む場合、極限は K = 3.45 log 7と書くこともできます。 （N）。

指数に複雑性があるというのは、今まで聞いたことがないことです。Z = B O(log(N))は、すべての十分に大きな N に対して Z ≤ B M ln(N)となるような定数 M が存在することを意味します。

于 2013-09-09T03:37:03.167 に答える
0

大きな問題を解決するときは、通常、それを小さな部分に分割します。いわゆる分割統治法です。たとえば、Quick Sort アルゴリズムでは、各フェーズで、サイズが十分に小さくなるまで配列のサイズが半分になり、解が得られます。些細なことになります。ここでは、各フェーズで問題のサイズが 2 で除算されるため、係数は 2 です。別の例を次に示します。

10 進数を文字列に変換する

while (n > 0) {
    digits.add(n % 10);
    n /= 10;
}
print digits.reverse();

各反復nは 10 分の 1 に減らされます。したがって、アルゴリズムの複雑さは O(log_10 n) です。たとえば、n = 1,000,000,000 の場合、アルゴリズムは最大で 9 ステップ = log_10 (1,000,000,000) 後に終了します。nが基数kにある場合、while10 をkに置き換えると、複雑度は O(log_k n) になります。

于 2013-09-10T13:19:40.300 に答える