BIG O 在没有足够信息的情况下
BIG O In absence of enough information
因此，假设您有一个函数 X(N)，它完全是一个黑盒子。你不知道函数的增长率，你查不到，你也看不到源码（目前）。
接下来让我们在另一个函数的上下文中检查它
for(int i = 0; i < N; ++i)
X(N);
您编写的代码是线性的，但显然函数 X 会影响 您的 函数的增长率。
例如，如果 X(N) 扩展为 for(int i = 0; i < N; ++i)，则您的函数是二次函数。
我的问题是：如果有人问你函数的Big O是什么，描述函数增长率的最佳方式是什么？
我说过我会称之为线性，我的回答辩护如下。
如果您知道 X 的实际增长率，您可以对您的代码做出准确的估计，但是虽然您可以（以某种方式）最终获得代码，但大多数函数并没有附带性能统计数据。
因此，如果您确实访问了 X 的代码，您可以将其包括在您的估计中，但是您在哪里划线？ X 可能还会调用其他函数，然后调用其他函数。我觉得在你处理完美划分代码的制造场景之外，如果你还不知道被调用的黑盒函数的增长率，你必须决定估计你能估计的代码。
你根本看不出来。只是没有足够的信息。除非 X(N) 是常数时间，否则说你的函数是线性的是错误的。
但是，您可以测量 X(N) 完成不同输入大小所花费的时间。通常这会给你一个粗略的估计它是如何渐近地表现的。
如果你想谈谈划清界限，我只想像这样说:-
代码的复杂度：- O(N*o(X))
一旦判断出函数X(N)的复杂度，就可以简单代入公式
到那时，它将是一个 shorthand 但总的来说很有用的符号，同时满足循环的复杂性。
首先，这是一个很好的问题。人们通常会忘记一个关键步骤：识别基本操作.
时间效率的理论分析
通过确定 基本操作 的重复次数作为输入大小的函数来分析时间效率。
基本操作：对算法运行时间贡献最大的操作
我们尝试 select 事情作为 基本操作 可以在 O(1) 时间内执行，或接近于此，实际上我们 select 通常是 sub-linear 操作。例如：
- 为变量赋值
- 查找数组中特定元素的值
- 比较两个值
- 增加一个值
- 加法、乘法等基本算术运算
例如，基本算术运算显然不是 O(1)。看到计算机科学的这个问题：https://cs.stackexchange.com/questions/1643/how-can-we-assume-that-basic-operations-on-numbers-take-constant-time
因此，我们在决定基本操作时近似 O(1)。
设C(n)为基本操作需要执行的次数。并设 execTime 为特定计算机上 基本操作 的执行时间。
然后我们可以通过以下方式估计算法的运行时间T(n)：
T(n) ≈ execTime * C(n)
如您所见，效率class（例如Big-O）仅取决于C(n)，因为execTime 无论如何都是常数（我们不关心渐近分析中的常数）。所以，任务是找到C(n).
分析你的代码
首先我们决定输入参数，显然是N.
然后我们决定基本操作，这是不同的部分。
如果我们决定X(N);作为基本操作，那么：
T(N) ≈ execTime * C(N)
C(N) = N
O(execTime * N) = O(n)
如果我们知道 X(N) 内部发生了什么，我们可以决定 基本操作 N次在每个X(N)操作例如，然后：
T(N) ≈ execTime * C(N)
C(N) = N * N
O(execTime * N * N) = O(N * N) = O(n^2)
我们也可以select整个循环作为基本操作:
T(N) ≈ execTime * C(N)
C(N) = 1
O(execTime * 1) = O(1)
那么哪个是正确的？他们都。哪一个有意义？这完全取决于您要进行的比较。
例如，在比较排序算法的性能时，基本操作是键比较，因为排序算法中最重要的工作就是比较键，所有的排序算法都会做键的比较，这样我们就可以相互比较了。
总而言之，您可以 select X(N) 作为 基本操作 并说算法复杂度是 O(N)。 X(N) 不一定是 O(1) 严格，正如我上面解释的，我们已经忽略了比 O(1) 更复杂的基本操作。这里真正重要的是你想做什么比较。
假设您想比较这两种算法。
for(int i = 0; i < N; ++i)
X(N);
和
for(int j = 0; j < N; j++)
for(int i = 0; i < N; ++i)
X(N);
在这里，如果你 select X(N) 作为基本操作 两者，你会比较苹果与苹果，你会评估 O(N) 与 O(N^2) 并且它将是 完美 很好。
如果因为 X(N) 不是 O(1) 而觉得不对，请考虑这个：
for(int i = 0; i < N; ++i)
System.out.print(N);
来自 Java 的简单打印方法。我们select它作为一个基本操作根本没有考虑，因为它只是一个打印语句，并假设它是O(1)。但事实并非如此。它的复杂度是 sub-linear，但绝对不是常量。打印所需的时间随着打印项目的大小（N 在本例中）的增长而增长。
那么，X(N) 或 System.out.println(N) 重要吗？
P.S。我没有发明上面的近似技术。我确实使用 this 书准备了答案，主要是第二章。推荐你看看
因此，假设您有一个函数 X(N)，它完全是一个黑盒子。你不知道函数的增长率，你查不到，你也看不到源码（目前）。
接下来让我们在另一个函数的上下文中检查它
for(int i = 0; i < N; ++i)
X(N);
您编写的代码是线性的，但显然函数 X 会影响 您的 函数的增长率。
例如，如果 X(N) 扩展为 for(int i = 0; i < N; ++i)，则您的函数是二次函数。
我的问题是：如果有人问你函数的Big O是什么，描述函数增长率的最佳方式是什么？
我说过我会称之为线性，我的回答辩护如下。
如果您知道 X 的实际增长率，您可以对您的代码做出准确的估计，但是虽然您可以（以某种方式）最终获得代码，但大多数函数并没有附带性能统计数据。
因此，如果您确实访问了 X 的代码，您可以将其包括在您的估计中，但是您在哪里划线？ X 可能还会调用其他函数，然后调用其他函数。我觉得在你处理完美划分代码的制造场景之外，如果你还不知道被调用的黑盒函数的增长率，你必须决定估计你能估计的代码。
你根本看不出来。只是没有足够的信息。除非 X(N) 是常数时间，否则说你的函数是线性的是错误的。
但是，您可以测量 X(N) 完成不同输入大小所花费的时间。通常这会给你一个粗略的估计它是如何渐近地表现的。
如果你想谈谈划清界限，我只想像这样说:-
代码的复杂度：- O(N*o(X))
一旦判断出函数X(N)的复杂度，就可以简单代入公式
到那时，它将是一个 shorthand 但总的来说很有用的符号，同时满足循环的复杂性。
首先，这是一个很好的问题。人们通常会忘记一个关键步骤：识别基本操作.
时间效率的理论分析
通过确定 基本操作 的重复次数作为输入大小的函数来分析时间效率。
基本操作：对算法运行时间贡献最大的操作
我们尝试 select 事情作为 基本操作 可以在 O(1) 时间内执行，或接近于此，实际上我们 select 通常是 sub-linear 操作。例如：
- 为变量赋值
- 查找数组中特定元素的值
- 比较两个值
- 增加一个值
- 加法、乘法等基本算术运算
例如，基本算术运算显然不是 O(1)。看到计算机科学的这个问题：https://cs.stackexchange.com/questions/1643/how-can-we-assume-that-basic-operations-on-numbers-take-constant-time
因此，我们在决定基本操作时近似 O(1)。
设C(n)为基本操作需要执行的次数。并设 execTime 为特定计算机上 基本操作 的执行时间。
然后我们可以通过以下方式估计算法的运行时间T(n)：
T(n) ≈ execTime * C(n)
如您所见，效率class（例如Big-O）仅取决于C(n)，因为execTime 无论如何都是常数（我们不关心渐近分析中的常数）。所以，任务是找到C(n).
分析你的代码
首先我们决定输入参数，显然是N.
然后我们决定基本操作，这是不同的部分。
如果我们决定X(N);作为基本操作，那么：
T(N) ≈ execTime * C(N)
C(N) = N
O(execTime * N) = O(n)
如果我们知道 X(N) 内部发生了什么，我们可以决定 基本操作 N次在每个X(N)操作例如，然后：
T(N) ≈ execTime * C(N)
C(N) = N * N
O(execTime * N * N) = O(N * N) = O(n^2)
我们也可以select整个循环作为基本操作:
T(N) ≈ execTime * C(N)
C(N) = 1
O(execTime * 1) = O(1)
那么哪个是正确的？他们都。哪一个有意义？这完全取决于您要进行的比较。
例如，在比较排序算法的性能时，基本操作是键比较，因为排序算法中最重要的工作就是比较键，所有的排序算法都会做键的比较，这样我们就可以相互比较了。
总而言之，您可以 select X(N) 作为 基本操作 并说算法复杂度是 O(N)。 X(N) 不一定是 O(1) 严格，正如我上面解释的，我们已经忽略了比 O(1) 更复杂的基本操作。这里真正重要的是你想做什么比较。
假设您想比较这两种算法。
for(int i = 0; i < N; ++i)
X(N);
和
for(int j = 0; j < N; j++)
for(int i = 0; i < N; ++i)
X(N);
在这里，如果你 select X(N) 作为基本操作 两者，你会比较苹果与苹果，你会评估 O(N) 与 O(N^2) 并且它将是 完美 很好。
如果因为 X(N) 不是 O(1) 而觉得不对，请考虑这个：
for(int i = 0; i < N; ++i)
System.out.print(N);
来自 Java 的简单打印方法。我们select它作为一个基本操作根本没有考虑，因为它只是一个打印语句，并假设它是O(1)。但事实并非如此。它的复杂度是 sub-linear，但绝对不是常量。打印所需的时间随着打印项目的大小（N 在本例中）的增长而增长。
那么，X(N) 或 System.out.println(N) 重要吗？
P.S。我没有发明上面的近似技术。我确实使用 this 书准备了答案，主要是第二章。推荐你看看