ヒープ配列を作成する時間の複雑さがO（nlogn）ではなくO（log（n！））ではないのはなぜですか？
Avi
挿入関数「insert（A、n）」を介したヒープへの新しい要素の挿入には、O（log n）時間がかかります（nは配列「A」の要素の数です）。挿入機能を以下に示します。
void insert(int A[], int n)
{
int temp,i=n;
cout<<"Enter the element you want to insert";
cin>>A[n];
temp=A[n];
while(i>0 && temp>A[(i-1)/2])
{
A[i]=A[(i-1)/2];
i=(i-1)/2;
}
A[i]=temp;
}
挿入関数の時間計算量はO（log n）です。
配列をヒープ配列に変換する関数は次のように与えられます。
void create_heap()
{
int A[50]={10,20,30,25,5,6,7};
//I have not taken input in array A from user for simplicity.
int i;
for(i=1;i<7;i++)
{
insert(A,i);
}
}
この関数の時間計算量はO（nlogn）であることが与えられました。
->ただし、挿入関数には、各呼び出しで比較する要素の最大「i」があります。つまり、ループの1回の実行における時間計算量は、各呼び出しでO（log i）です。
->つまり、最初はlog1、次にlog2、次にlog3というように、log6まで続きます。
->したがって、配列のn個の要素の場合、合計時間計算量はlog2 + log3 + log4 + .... lognになります。
->これはlog（2x3x4x ... xn）= log（n！）になります
では、なぜ時間計算量はO（log（n！））ではなくO（nlogn）なのですか？
トニー・タナス
Log（n！）は、ログルールのn * lognからlog（n ^ n）によって制限されます。
1*2*3*4*....*n = n!
n*n*n*n*....*n = n^n
明らかにn！<n ^ n
それでは、なぜより厳しい境界があるO(nlogn)ときに使用するのO(logn!)ですか？nlognlog（n！）で囲まれているので、驚くべきことではありませんか？
log(1*2*3*4*....*n) = log(1) + log(2) + ... + log(n)
前半は捨てましょう
log(1*2*3*4*....*n) > log(n/2) + log((n/2) + 1) + log((n/2)+2) + ... + log(n)
> log(n/2) + log(n/2) + ... + log(n/2)
= n/2*log(n/2) = O(nlogn)
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
編集
関連記事
Related 関連記事
- 1
ヒープソートO（nlogn）の時間計算量はなぜですか？
- 2
Θ（n）ではなく2つのnサイズのソートされた配列O（n）をマージする時間の複雑さはなぜですか？
- 3
ハッシュテーブルの挿入時間の複雑さが最悪の場合がNlogNではないのはなぜですか
- 4
順序付けられていない配列では、要素O（n）を削除する時間の複雑さではありませんか？
- 5
なぜループではないO（N * 2 ^ n）のための2の時間複雑さはありますか？
- 6
aが整数の配列で、nが配列の長さである場合、O（sum（a））の全体的なO（n）時間計算量はどれくらいですか？
- 7
これらのループとハッシュ操作にO（N）時間の複雑さが必要なのはなぜですか？
- 8
forループを使用するフィボナッチの時間計算量がO（n）ではなくO（n ^ 2）であるのはなぜですか？
- 9
なぜこのメソッドの時間の複雑さは2 * O（n log n）+ O（m log m）なのですか？
- 10
なぜ基数ソートはO（k + n）の空間複雑性を持っているのですか？
- 11
ソートが時間内にO（n log（n））を取らないのはなぜですか
- 12
Javaがjavadocに各関数の時間/空間の複雑さを含めないのはなぜですか？
- 13
配列挿入の時間計算量がO（n + 1）ではなくO（n）であるのはなぜですか？
- 14
最小ヒープの削除の最悪の場合のランタイムが配列O（N）として実装されているのはなぜですか？
- 15
文字列を有効な単語に分割する時間の複雑さはどれくらいですか？
- 16
O（n）ではなく再帰的順序トラバーサルO（h）の空間の複雑さはなぜですか
- 17
配列の要素をマップに挿入する時間の複雑さはどれくらいですか？
- 18
n個のユニオン検索（サイズによるユニオン）操作を実行する時間の複雑さがO（n log n）であるのはなぜですか？
- 19
なぜ「ε」ではなく「=」がアルゴリズムの時間複雑性を表現するのに使用されるのですか?
- 20
このループがO（n log n）ではなくO（n log log n）の値を返すのはなぜですか？
- 21
問題は、ソートされていない配列から重複を削除し、時間内の順序を維持することですO（N）
- 22
ヒープの構築はどのようにしてO（n）時間の複雑さになるのでしょうか？
- 23
空の配列を作成すると、Javascriptが出力[（...）]ではなく（...）に表示されるのはなぜですか？
- 24
なぜlist.addとネストされたループはO（N ^ 4）時間の複雑さを与えるのでしょうか？
- 25
複雑なデータのコピーに時間がかかるのはなぜですか
- 26
時間の複雑さO（（log（N））^ 2）はO（sqrt（N））と同等ですか？
- 27
キーワークを使用しながら辞書のキー値を検索する時間の複雑さはどれくらいですか？
- 28
次の擬似コードの実行時の複雑さ（大きなO）はどれくらいですか？
- 29
アルゴリズムの複雑さがO（log log n）になる原因は何ですか？
コメントを追加