什么是大 O 时间复杂度？

该博客上撰写的文章是出于教学目的而创建的。 另外，文章中的信息可能不正确，请谨慎。

大 O 表示法表示计算量随着输入大小的增加而增加的速率。 其目的与准确告知需要多少纳秒的基准不同。

常见的复杂性

O(1) 数组索引访问
O(log N) 二分查找
O(N) 完全遍历
O(N log N) 一般比较排序
O(N²) 比较所有对

常量被省略

for (int Value : Values)
{
    ProcessA(Value);
}

for (int Value : Values)
{
    ProcessB(Value);
}

由于遍历了两次，所以实际操作是2N靠近，但在 Big OO(N)将其表达为 这是因为它关注的是随着 N 的增长而递增的顺序。

忽略常量并不意味着它们在实际性能中不重要。 缓存友好O(N)如果您的代码与复杂常量不同O(N)它可以比代码快得多。

最差、平均、最好

线性搜索找到第一个元素O(1)，但如果它丢失或位于末尾O(N)是。 如果你不写下你在谈论哪种情况，同样的算法将会有不同的解释。

Big O 是选择算法的第一个过滤器。 最终选择应根据实际数据大小、内存使用情况、缓存和实现复杂性进行权衡。