gpt4 book ai didi

algorithm - 为什么 ArrayList 在 O(n) 而不是 O(n*n) 中删除功能

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:14:53 25 4
gpt4 key购买 nike

请问下面Remove函数的时间复杂度是O(n)还是O(n*n)?

它删除集合中第一个值与提供的值匹配的项,如果删除了一个值,则返回 true。否则返回 false

public bool Remove(T item) 
{
for (int i = 0; i < Count; i++)
{
if (_items[i].Equals(item))
{
RemoveAt(i);
return true;
}
}
return false;
}

public void RemoveAt(int index)
{
if (index >= Count)
{
throw new Exception("Index out of Range");
}

var sourceIndex = index + 1;
Array.Copy(_array, sourceIndex, _array, index, _array.Length - sourceIndex);

Count--;
}

最佳答案

public bool Remove(T item) 
{
for (int i = 0; i < Count; i++) // say count = n. this loop will run n times.
{
if (_items[i].Equals(item)) // say if operation takes 10 units of time
{
RemoveAt(i);
return true; // say this operation takes 2 units of time
}
}
return false; // say this operation takes 2 units of time
}

public void RemoveAt(int index) {
if (index >= Count) // say this operation takes 10 units of time
{
throw new Exception("Index out of Range"); // say this operation takes 4 units of time
}

var sourceIndex = index + 1; // say this operation takes 2 units of time
Array.Copy(_array, sourceIndex, _array, index, _array.Length - sourceIndex); // say this operation takes 10 units of time

Count--; // say this operation takes 5 units of time
}

这意味着 RemoveAt 需要 10 + 4 + 2 + 10 + 5 个时间单位 = 31 个时间单位而 Remove 需要 n * (10 + 31 + 2) 个时间单位 = n * 43 个时间单位。

任何需要固定时间量的操作都称为 O(1) 操作。因此,Remove 需要 n * O(1) 时间单位,其数量级为 O(n)

关于algorithm - 为什么 ArrayList 在 O(n) 而不是 O(n*n) 中删除功能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48717823/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com