情報系総合質問スレ
■ このスレッドは過去ログ倉庫に格納されています
0812名無しさん＠お腹いっぱい。
2009/07/23(木) 12:40:46ID:ZpQWnox90要素の追加、削除の仕方よりヒープ木は平衡。よって深さはlog n
ソートはヒープ木からルート要素の削除(O(log n))をn回行うだけ。
ヒープ木を作成するには追加(O(log n))をn回行えば良いからO(nlog n)。
よって時間計算量はO(nlog n)。
■ このスレッドは過去ログ倉庫に格納されています
要素の追加、削除の仕方よりヒープ木は平衡。よって深さはlog n
ソートはヒープ木からルート要素の削除(O(log n))をn回行うだけ。
ヒープ木を作成するには追加(O(log n))をn回行えば良いからO(nlog n)。
よって時間計算量はO(nlog n)。