如何找到算法的操作时间？
How to find Operation TIme of an Algoritm?
我正在学习如何找到算法的运行时间，但在这张图片中我不明白 1 + 2n + 2(n-1) 是什么意思。
以及这些方程式的来源
基本上，编写这些幻灯片的人认为尝试变得更“准确”是个好主意，即使它们并不准确（而且尝试可能是个坏主意）。
第 1 行
for (i = 0; i < n-1; i++)
i = 0 只执行一次（我们不会一直初始化 i）。所以这算作：
1
i < n-1 在循环开始之前、每次迭代之间和最后一次迭代之后执行（这就是它知道如何退出的方式）。所以这算作：
number of iterations + 1
= num_elements{0, ..., n-2} + 1
= (n-1) + 1
= n
i++ 在每次迭代后执行（这次不是在第一次迭代期间）。所以这算作：
number of iterations
= n - 1
全部：
(1) + (n) + (n-1)
现在，这与您的讲座幻灯片上的内容不同，因为您的讲师已决定：
i < n-1
真的是：
int tmp_max = n - 1; i < tmp_max;
所以他们认为这实际上是两个操作，即使编译器只会 pre-compute 这个值一次（在循环之前）。对于像你这样的学生来说，它也不必要地混淆了事情。
他们一定也认为：
i++
真的是
i = i + 1
或者，换句话说：
int tmp_i = i + 1; i = tmp_i
同样，他们误解了 c/c++ 编译器的工作方式。 i++ 现在总是等同于 ++i，它不使用任何临时值，因此只出现在一个时钟周期内。
迷茫？当你学习复杂性理论时，你不应该关心这些东西。一次加法只需要一个时钟周期，但在大多数现代 CPU 上除法大约需要 5 个时钟周期，但我怀疑你的老师希望你考虑 that。当您研究复杂性时，您不应该研究处理器。复杂性理论的全部要点是你不关心这些乘法常数。
我们关心的是i从0到n（谁在乎n-1），这条线的复杂度是：
O(n).
第 2 行
for (j = 0; j < n-i-1; j++)
他们在决定乘法常数时也有同样糟糕的推理，这次每个 j < n-i-1 被你的老师认为是 3 次运算。
至于内在的部分，这个是有道理的，只是作者没有把问题分开。
我们应该先 计算这条线的复杂度，就好像 i 是一个常数：
1 + (n-i) + (n-i)
= O(n-i)
然后记住 j 值将从 0 变为 n-i。
剩余行数
这些是常数时间。无论 n、i 或 j 的值如何，程序都可以只执行 if 语句，也可以执行所有 4 行。
O(1)
总计：
Outer loop, i = {0, ..., n}, O(n)
inner loop, j = {0, ..., n - i}, O(n-i)
inside loop, O(1)
让我们移除模块化并认识到 i 不是常数：
complexity of the two loops = O(n-0) + O(n-1) + ... + O(0)
= O(1 + 2 + 3 ... + n)
= O(n(n+1)/2)
= O(n^2)
我猜你已经知道 how to find the sum of:
1 + 2 + 3 ... + n
那么内循环执行了多少次呢？与第二个循环的迭代次数一样多 - 由于其内容的复杂性与循环的复杂性无关，我们可以乘以：
overall complexity = O(n^2) * O(1)
= O(n^2)
希望我对模块化计算的解释对您有所帮助。它对于更大的示例非常有用——尤其是真实的代码库。大多数时候，您在模块化组件之间没有依赖关系，因此您可以只添加或增加组件 - 希望我已经证明即使您有依赖关系，模块化仍然有用。
我正在学习如何找到算法的运行时间，但在这张图片中我不明白 1 + 2n + 2(n-1) 是什么意思。 以及这些方程式的来源
基本上，编写这些幻灯片的人认为尝试变得更“准确”是个好主意，即使它们并不准确（而且尝试可能是个坏主意）。
第 1 行
for (i = 0; i < n-1; i++)
i = 0 只执行一次（我们不会一直初始化 i）。所以这算作：
1
i < n-1 在循环开始之前、每次迭代之间和最后一次迭代之后执行（这就是它知道如何退出的方式）。所以这算作：
number of iterations + 1
= num_elements{0, ..., n-2} + 1
= (n-1) + 1
= n
i++ 在每次迭代后执行（这次不是在第一次迭代期间）。所以这算作：
number of iterations = n - 1
全部：
(1) + (n) + (n-1)
现在，这与您的讲座幻灯片上的内容不同，因为您的讲师已决定：
i < n-1
真的是：
int tmp_max = n - 1; i < tmp_max;
所以他们认为这实际上是两个操作，即使编译器只会 pre-compute 这个值一次（在循环之前）。对于像你这样的学生来说，它也不必要地混淆了事情。
他们一定也认为：
i++
真的是
i = i + 1
或者，换句话说：
int tmp_i = i + 1; i = tmp_i
同样，他们误解了 c/c++ 编译器的工作方式。 i++ 现在总是等同于 ++i，它不使用任何临时值，因此只出现在一个时钟周期内。
迷茫？当你学习复杂性理论时，你不应该关心这些东西。一次加法只需要一个时钟周期，但在大多数现代 CPU 上除法大约需要 5 个时钟周期，但我怀疑你的老师希望你考虑 that。当您研究复杂性时，您不应该研究处理器。复杂性理论的全部要点是你不关心这些乘法常数。
我们关心的是i从0到n（谁在乎n-1），这条线的复杂度是：
O(n).
第 2 行
for (j = 0; j < n-i-1; j++)
他们在决定乘法常数时也有同样糟糕的推理，这次每个 j < n-i-1 被你的老师认为是 3 次运算。
至于内在的部分，这个是有道理的，只是作者没有把问题分开。
我们应该先 计算这条线的复杂度，就好像 i 是一个常数：
1 + (n-i) + (n-i) = O(n-i)
然后记住 j 值将从 0 变为 n-i。
剩余行数
这些是常数时间。无论 n、i 或 j 的值如何，程序都可以只执行 if 语句，也可以执行所有 4 行。
O(1)
总计：
Outer loop, i = {0, ..., n}, O(n)
inner loop, j = {0, ..., n - i}, O(n-i)
inside loop, O(1)
让我们移除模块化并认识到 i 不是常数：
complexity of the two loops = O(n-0) + O(n-1) + ... + O(0)
= O(1 + 2 + 3 ... + n)
= O(n(n+1)/2)
= O(n^2)
我猜你已经知道 how to find the sum of:
1 + 2 + 3 ... + n
那么内循环执行了多少次呢？与第二个循环的迭代次数一样多 - 由于其内容的复杂性与循环的复杂性无关，我们可以乘以：
overall complexity = O(n^2) * O(1)
= O(n^2)
希望我对模块化计算的解释对您有所帮助。它对于更大的示例非常有用——尤其是真实的代码库。大多数时候，您在模块化组件之间没有依赖关系，因此您可以只添加或增加组件 - 希望我已经证明即使您有依赖关系，模块化仍然有用。