15/12/18 03:49:05.07 bQYD5Sab.net
ただ、vectorは、末尾の要素の追加・削除は、計算量O(1)だけど、
要素の中ほどに追加すると、
それ以降の要素が1つずつずれるから、O(n)になる
Doubly Linked Listなら、そういうときにO(1)。
ただ、これは基本、1つずつ要素をたぐっていく、
シーケンシャルアクセスだから、要素の取得はO(n)
vectorの要素の取得は、数値インデックスで、
O(1)のランダムアクセスができる
15/12/18 03:49:05.07 bQYD5Sab.net
ただ、vectorは、末尾の要素の追加・削除は、計算量O(1)だけど、
要素の中ほどに追加すると、
それ以降の要素が1つずつずれるから、O(n)になる
Doubly Linked Listなら、そういうときにO(1)。
ただ、これは基本、1つずつ要素をたぐっていく、
シーケンシャルアクセスだから、要素の取得はO(n)
vectorの要素の取得は、数値インデックスで、
O(1)のランダムアクセスができる