動的配列の償却時間

単純な例として、動的配列の特定の実装では、配列がいっぱいになるたびに配列のサイズを2倍にします。このため、配列の再割り当てが必要になることがあります。最悪の場合、挿入にはO（n）が必要です。しかし、残りの挿入は一定の時間内に行われるので、n個の挿入はO（n）時間で完了することができます。したがって、オペレーションごとの償却された時間は、O（n）/ n = O（1）です。 --with Wiki動的配列の償却時間

しかし、別の本では：各倍増はO（n）時間かかるが、その償却時間は依然としてO（1）であることはめったにない。

誰かが私に稀な状況を教えてくれるのですが、Wikiの説明を推測できますか？ありがとう

出典

2011-01-31 laynece

「他の著書」言っていないものである理由です。つまり、それはウィキが言った記述の曖昧で不正確な方法です。これはあなたの宿題ですか？あなた自身の分析に従ってください;） –

はい、これらの2つのステートメントは同じことを言いますが、Wikiはそれをより完全に説明しています。

出典

2011-01-31 17:32:35

基本的には、償却額は操作数あたりの平均を意味します。

したがって、nの配列がある場合、再割り当てが必要になるまでn + 1個のアイテムを挿入する必要があります。

だから、あなたはn個のインサートそれらの一つ一つがかかったをやったO（1）、および合計であなたがのn + 1を持っているので、O（n）のを取った別のインサートは、2n操作です。

2n/n+1 ~= 1

は償却時間はまだO（1）

出典

2011-01-31 17:35:55

費用はここで2n + 1であってはなりませんか？ –

答えて

関連する問題