列表的大O调整大小

Question

这个问题适用于所有语言,但让我坚持使用C#

var names = new List<string> {"Jerry", "Cosmo", "Elaine", "George"};

这是我的编译时间列表.如果我决定在其中插入记录,那么下面的.Net将长度从4增加到8.

names.Insert("Newman");

上面这个插入方法的Big-O会变成O(N)吗？哪个N作为列表的长度？如果是的话,大多数面试官真的关心吗？

编辑

让我们说我们正在插入1000条记录.长度将在4,8,16,32加倍....所以插入复杂度将是Log(N)正确吗？

Answer 1

该特定插入操作的复杂性(其中列表的大小加倍)是O(N).但是,摊销的复杂性仍然是O(1),因为列表N / 2之前的元素大小没有加倍,因此每次插入的平均操作数仍然是不变的.面试官可能希望你意识到这种差异.