performance - O(N) 是什么意思

Question

这个问题在这里已经有了答案:




11 年前关闭。

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符号。

简要地:

O(1) 表示在恒定时间内 -
与项目数量无关。

O(N) 表示与
东西的个数。

O(log N) 表示时间与
日志(N)

基本上任何“O”符号都意味着一个操作最多需要 k*f(N)
在哪里:

k is a constant multiplier

f() is a function that depends on N