performance - BIG O 在缺乏足够信息的情况下

Question

所以，假设你有一个函数，X(N)那是一个完全的黑匣子。你不知道函数的增长率，查不到，也查不到源码(目前)。

接下来让我们在另一个函数的上下文中检查它

for(int i = 0; i < N; ++i)
    X(N);

你写的代码是线性的，但显然是函数 X对函数的增长率有影响。
例如，如果 X(N)扩展为 for(int i = 0; i < N; ++i)你的函数是二次的。

我的问题是:如果有人问您函数的大 O 是什么，那么描述函数增长率的最佳方式是什么？

我说我会称之为线性，我的答案的辩护如下。

如果你知道X的实际增长率，您可以准确估计您的代码，尽管您可以(以一种或另一种方式)最终获得代码，但大多数函数并没有附带性能统计信息。

因此，如果您确实可以访问 X 的代码，你可以把它包括在你的估计中，但是你在哪里划线？ X可能还调用其他函数，然后调用其他函数。我觉得在你处理完美划分代码的制造场景之外，如果你还不知道被调用的黑盒函数的增长率，你必须决定估计你可以估计的代码。

Answer 1

如果您要谈论划线，我只想提供以下内容:-

代码的复杂性:- O(N*o(X))
一旦判断出函数X(N)的复杂度，就可以简单地代入公式。

到那时，它将是一个速记但有用的符号，同时满足循环的复杂性。