两次通过数组 O(n) 或 O(2n)
Two passes through an array O(n) or O(2n)
我在面试蛋糕上练习了一些问题，在问题 2 上给出的解决方案使用了两个单独的 for 循环（未嵌套），解决方案提供者声称 he/she 在 O( n) 时间。据我了解，这将是 O(2n) 时间。是我想错了，还是方案提供者有误？
采访蛋糕摘录：
Big-O 表示法对于查看代码的缩放方式最有用。也就是说，如果我将数组的大小加倍，代码需要多长时间才能 运行？如果您的代码是 O(n)，则需要两倍的时间，而如果是 O(n^2)，则需要 4 倍的时间，依此类推。在这种情况下，无论您通过循环两次，将数组的大小加倍所花费的时间是以前的两倍（每个循环的时间都是原来的两倍）。
大 O 符号提示您算法执行时间如何取决于输入数据。当您看到时间复杂度为 O(n) 时，您就会明白输入和执行时间之间存在 线性 依赖关系。没有提到常量。
根据定义 O(g(n)) 是一个 函数集 对于每个函数，以下语句成立：存在这样的正常数 c 和 n0 使得 0 ≤ f(n) ≤ cg(n) 对所有 n ≥ n0 成立。你看到定义使用了一个任意常数 c，如果你的 g(n) 本身有一个不会有任何区别的常数。
最终我们有：O(cg(n)) = O(g(n))。在您的特定情况下 O(cn) = O(2n) = O(n)。它们都代表同一组函数。
我在面试蛋糕上练习了一些问题，在问题 2 上给出的解决方案使用了两个单独的 for 循环（未嵌套），解决方案提供者声称 he/she 在 O( n) 时间。据我了解，这将是 O(2n) 时间。是我想错了，还是方案提供者有误？
采访蛋糕摘录：
Big-O 表示法对于查看代码的缩放方式最有用。也就是说，如果我将数组的大小加倍，代码需要多长时间才能 运行？如果您的代码是 O(n)，则需要两倍的时间，而如果是 O(n^2)，则需要 4 倍的时间，依此类推。在这种情况下，无论您通过循环两次，将数组的大小加倍所花费的时间是以前的两倍（每个循环的时间都是原来的两倍）。
大 O 符号提示您算法执行时间如何取决于输入数据。当您看到时间复杂度为 O(n) 时，您就会明白输入和执行时间之间存在 线性 依赖关系。没有提到常量。
根据定义 O(g(n)) 是一个 函数集 对于每个函数，以下语句成立：存在这样的正常数 c 和 n0 使得 0 ≤ f(n) ≤ cg(n) 对所有 n ≥ n0 成立。你看到定义使用了一个任意常数 c，如果你的 g(n) 本身有一个不会有任何区别的常数。
最终我们有：O(cg(n)) = O(g(n))。在您的特定情况下 O(cn) = O(2n) = O(n)。它们都代表同一组函数。