algorithm - 关于大 O 符号和复杂性

Question

我目前正在学习 Big O Notations，但我对根据不同复杂性进行的时间/迭代计算有点困惑。

我做了这个问题:

An algorithm that goes through all possible solutions takes 10^(-7) seconds with each test. If the number of solutions are the following functions: logn, n, nlog. n^2, what's the maximum n I can calculate in, for example, less than 1 second?

我认为(对于 case logn)是 10^-7 次 logn 必须少于 1 秒:

10^(-7) * logn < 1 <=> n = 10^(1/10^-7)

难以置信的大(如果没记错的话，该死的——')。但是 n^2 呢？

10^(-7) * n^2 < 1 <=> n = square_root(1/10^-7)

但是，如果复杂度更大，n^2 情况下的解决方案数量怎么会少于 n 情况下的数量呢？这让我感到困惑...？

Answer 1

“这在很多层面上都很糟糕。”

首先，O(f(n)) 与 f(n) 不同。

复杂性通常用于表示解决问题所需的时间，作为输入大小的函数。

当然如果您可以使用 X vs Y 在相同的时间内解决更多的问题，那么 X 将在固定的时间内比 Y 解决更多的问题。但是由于您没有使用如果以正确的方式使用术语复杂性，您会得到(看似)自相矛盾的答案也就不足为奇了。