performance - O(N) 是什么意思

Question

这个问题已经有答案了:

已关闭 13 年前。

Possible Duplicate:
What is Big O notation? Do you use it?

大家好，

相当基本的可扩展性符号问题。

我最近收到了一篇关于我的 python 有序列表实现的帖子的评论“但请注意，插入的‘有序集’实现是 O(N) 的”

很高兴知道这一点，但我不确定这意味着什么。

我见过诸如 n(o) o(N)、N(o-1) 或 N(o*o) 之类的符号

上面的符号指的是什么？

Answer 1

该评论指的是 Big-O符号。

简单地说:

1. O(1) 表示在常数时间内 -与项目数量无关。
2. O(N) 表示与项目数量。
3. O(log N) 表示时间正比于日志(N)

基本上任何“O”符号都意味着操作最多需要 k*f(N)
其中:

k is a constant multiplier

f() is a function that depends on N