复制操作的大 O 表示法
我遇到了一些肯定可以改进的代码，但我想知道我的改进的 Big-O 表示法。
他们的原始代码向数组添加一个元素，每次执行此操作时，都会创建一个 n+1 的新数组并复制旧数组，如下所示：
public MyType GetNewType()
{
MyType[] tempTypes = new MyType[_types.Count + 1];
_types.CopyTo(tempTypes, 0);
_types = tempTypes;
_types[types.Count - 1] = new MyType();
return _types[types.Count - 1];
}
据我所知，这将是一个 O(n) 操作。因此，我将其重写如下：
private int _currentIndex; //initialized in the constructor
public MyType GetNewType()
{
if (_types.Length == _currentIndex)
{
MyType[] tempTypes = new MyType[_types.Length + 10];
_types.CopyTo(tempTypes, 0);
_types = tempTypes;
}
_types[_currentIndex] = new MyType();
_currentIndex++;
return _types[_currentIndex - 1];
}
这些更改的结果是否意味着该函数现在将以 O(n / 10) 的速度运行，因为它只需要每 10 次调用进行一次复制操作？或者它的效果并不那么好？
I've come across some code which could definitely be improved, but i'm wondering about the Big-O notation of my improvements.
Their original code adds a element to an array, and each time it does this it creates a new array of n+1 and copies the old one in like so:
public MyType GetNewType()
{
MyType[] tempTypes = new MyType[_types.Count + 1];
_types.CopyTo(tempTypes, 0);
_types = tempTypes;
_types[types.Count - 1] = new MyType();
return _types[types.Count - 1];
}
As far as I can see this would be a O(n) operation. I therefore rewrote it as follows:
private int _currentIndex; //initialized in the constructor
public MyType GetNewType()
{
if (_types.Length == _currentIndex)
{
MyType[] tempTypes = new MyType[_types.Length + 10];
_types.CopyTo(tempTypes, 0);
_types = tempTypes;
}
_types[_currentIndex] = new MyType();
_currentIndex++;
return _types[_currentIndex - 1];
}
Would the result of these changes mean that the function will now run in O(n / 10) as it would only require a copy operation every 10 calls? Or does it not quite work as nicely as that?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
就 Big-O 表示法而言，
(n/10)的复杂度将为O(n)，因为它不关心如此小的常量。In terms of Big-O notation complexity of the
(n/10)would beO(n)because it does not care such a small constants.这是一个常见且很好的优化。它通常被称为“摊余常数时间”，这意味着大多数时候，添加单个元素的时间复杂度为 O(1)，除非不是。通常，实现者会将数组的大小加倍，或者至少乘以 1.5，而不是仅添加 10 个元素。
也就是说，C# 有一些非常可爱的内置列表类，它们会自动为您完成这一切，并且尽可能使用它们优于使用裸数组。
This is a common and good optimization. It's usually called "amortized constant time", which means most of the time, it's O(1) to add a single element, except when it's not. Often implementors will double the size of the array, or at least multiply by 1.5, instead of just adding ten elements.
That said, C# has some perfectly lovely built-in list classes which do this all for you, automagically, and using them is to be preferred over using bare arrays, whenever possible.
仅当每次用完免费项目时将数组大小加倍时，摊销常数时间才有效！
如果不是，平均大 O 表示法将始终为 O(n)。
每次列表计数等于容量时，C# 列表实现都会将数组大小加倍。
为了使你的插入方法平均 O(1)，你需要这样：
Amortized constant time works only if you DOUBLE the size of the array each time you run out of free items!
If not, averaged big O notation will be always O(n).
C# List implementation doubles the size of the array each time the list count is equal to capacity.
To make your insertion method averaged O(1) you need to so something like this: