采用最高项的算法的时间复杂度
Time complexity of an algorithm taking highest term
在分析算法的时间复杂度时，为什么只取最高增长项？
我的想法是，时间复杂度一般不被用作算法性能的准确度量，而是用于识别算法属于哪个组。
考虑一下，如果您有单独的循环，但每个循环都有两层的嵌套循环，都迭代 n 个项目，使得算法的总复杂度为 2n^2
为什么说这个算法复杂度为O(n^2)？
而不是 O(2n^2)
我的其他想法是，n^2 定义了计算与输入长度图的形状，或者我们在计算复杂度时考虑并行计算，使得 O(2n^2) = O(n^2)
确实 Ax^2 只是 x^2 的缩放，形状仍然是二次的
我的另一个问题是考虑相同的两个独立循环，现在第一个迭代 n 个项目，第二个迭代 v 个项目，这样如果使用顺序计算，算法的总复杂度为 n^2 + v^2。复杂度会是O(n^2+v^2)吗？
谢谢
所以首先让我观察一下，如果一个循环在循环体中的工作量是其两倍以上，则两个循环可能比一个循环更快。
为了完整回答您的问题，big-O 描述了一个增长机制，但它没有描述什么 我们观察到的增长。通常的假设是类似于处理器周期或机器指令，您还可以仅计算浮点运算（在科学计算中很常见）、内存读取（探测复杂度）、缓存未命中，应有尽有。
你想算机器操作，没人拦着你。但是，如果您不使用大 O 表示法，那么您必须具体说明是哪台机器以及哪种实现。 Don Knuth 为计算机编程艺术发明了一种著名的汇编语言，因此他可以做到这一点。
不过这需要做很多工作，因此算法研究人员通常会效仿 Angluin——Valiant，后者引入了单位成本 RAM。他们的假设是这样的：对于当时的任何一对计算机，您都可以编写一个程序来模拟其中一个源指令使用恒定数量的目标指令。因此，通过使用 big-O 擦除前导常量，您可以对大型 class 机器进行声明。
区分广泛的 classes 算法仍然很有用。在一个古老但特别令人难忘的演示中，Jon Bentley 展示了 TRS-80（低端微型计算机）上的线性时间算法可以击败 Cray 1（当时最快的超级计算机）上的三次算法。
回答另一个问题：是的，如果我们不知道是 n 还是 v 占主导地位，O(n² + v²) 是正确的。
您正在使用 big-O 表示法来表示时间复杂度，它给出了 渐近上限 。
对于函数 f(n)，我们将 O(g(n)) 定义为函数集
O(g(n)) = { f(n): there exist positive constants c and n0
such that,
0 ≤ f(n) ≤ cg(n) for all n ≥ n0}
现在开始质疑，
In the analysis of the time complexity of algorithms, why do you take only the highest growing term?
考虑一个算法，f(n) = an2 +bn +c
它的时间复杂度由 O(n2) 或 f(n) = O(n2)
因为总会有常数 c' 和 n0 使得 c'g(n) ≥ f(n) 即 c'n2 ≥ an2 +bn +c ，对于 n ≥ n0
我们只考虑更高的增长期 an2 并忽略 bn+c 作为 long term an2将比 bn +c 大 (eg.for n=1020, n2 比 n)
大 1020 倍
Why is it taken that this algorithm is complexity of O(n^2)? rather than O(2n^2)
当一个常量乘以一个常量时，它会按常量缩放函数，因此即使 2n2 > n2 我们将时间复杂度写为 O(n2) 因为存在一些常量 c', n0 使得 c'n2≥2n2
Will the complexity be O(n^2+v^2)
是，时间复杂度会是O(n2 + v2) 但如果一个变量占主导地位，它将是 O(n2) 或 O(v2) 取决于哪个占主导地位。
My thoughts are that time complexity is generally not used as an accurate
measurement of the performance of an algorithm but rather used to identify
which group an algorithm belongs to.
时间复杂度用于根据函数的增长来估计性能。算法的确切性能很难精确确定，因此我们依靠渐近边界来获得关于大输入性能的粗略想法
您可以考虑合并排序 (O(NlgN)) 和插入排序 (O(N2)) 的情况。很明显，就性能而言，合并排序优于插入排序，因为 NlgN < N2 但当输入大小较小时（例如 N=10），插入排序优于合并排序，主要是因为常量合并排序中的操作会增加它的执行时间。
在分析算法的时间复杂度时，为什么只取最高增长项？
我的想法是，时间复杂度一般不被用作算法性能的准确度量，而是用于识别算法属于哪个组。
考虑一下，如果您有单独的循环，但每个循环都有两层的嵌套循环，都迭代 n 个项目，使得算法的总复杂度为 2n^2
为什么说这个算法复杂度为O(n^2)？ 而不是 O(2n^2)
我的其他想法是，n^2 定义了计算与输入长度图的形状，或者我们在计算复杂度时考虑并行计算，使得 O(2n^2) = O(n^2)
确实 Ax^2 只是 x^2 的缩放，形状仍然是二次的
我的另一个问题是考虑相同的两个独立循环，现在第一个迭代 n 个项目，第二个迭代 v 个项目，这样如果使用顺序计算，算法的总复杂度为 n^2 + v^2。复杂度会是O(n^2+v^2)吗？
谢谢
所以首先让我观察一下，如果一个循环在循环体中的工作量是其两倍以上，则两个循环可能比一个循环更快。
为了完整回答您的问题，big-O 描述了一个增长机制，但它没有描述什么 我们观察到的增长。通常的假设是类似于处理器周期或机器指令，您还可以仅计算浮点运算（在科学计算中很常见）、内存读取（探测复杂度）、缓存未命中，应有尽有。
你想算机器操作，没人拦着你。但是，如果您不使用大 O 表示法，那么您必须具体说明是哪台机器以及哪种实现。 Don Knuth 为计算机编程艺术发明了一种著名的汇编语言，因此他可以做到这一点。
不过这需要做很多工作，因此算法研究人员通常会效仿 Angluin——Valiant，后者引入了单位成本 RAM。他们的假设是这样的：对于当时的任何一对计算机，您都可以编写一个程序来模拟其中一个源指令使用恒定数量的目标指令。因此，通过使用 big-O 擦除前导常量，您可以对大型 class 机器进行声明。
区分广泛的 classes 算法仍然很有用。在一个古老但特别令人难忘的演示中，Jon Bentley 展示了 TRS-80（低端微型计算机）上的线性时间算法可以击败 Cray 1（当时最快的超级计算机）上的三次算法。
回答另一个问题：是的，如果我们不知道是 n 还是 v 占主导地位，O(n² + v²) 是正确的。
您正在使用 big-O 表示法来表示时间复杂度，它给出了 渐近上限 。
对于函数 f(n)，我们将 O(g(n)) 定义为函数集
O(g(n)) = { f(n): there exist positive constants c and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}
现在开始质疑，
In the analysis of the time complexity of algorithms, why do you take only the highest growing term?
考虑一个算法，f(n) = an2 +bn +c
它的时间复杂度由 O(n2) 或 f(n) = O(n2)
因为总会有常数 c' 和 n0 使得 c'g(n) ≥ f(n) 即 c'n2 ≥ an2 +bn +c ，对于 n ≥ n0
我们只考虑更高的增长期 an2 并忽略 bn+c 作为 long term an2将比 bn +c 大 (eg.for n=1020, n2 比 n)
大 1020 倍
Why is it taken that this algorithm is complexity of O(n^2)? rather than O(2n^2)
当一个常量乘以一个常量时，它会按常量缩放函数，因此即使 2n2 > n2 我们将时间复杂度写为 O(n2) 因为存在一些常量 c', n0 使得 c'n2≥2n2
Will the complexity be O(n^2+v^2)
是，时间复杂度会是O(n2 + v2) 但如果一个变量占主导地位，它将是 O(n2) 或 O(v2) 取决于哪个占主导地位。
My thoughts are that time complexity is generally not used as an accurate
measurement of the performance of an algorithm but rather used to identify
which group an algorithm belongs to.
时间复杂度用于根据函数的增长来估计性能。算法的确切性能很难精确确定，因此我们依靠渐近边界来获得关于大输入性能的粗略想法
您可以考虑合并排序 (O(NlgN)) 和插入排序 (O(N2)) 的情况。很明显，就性能而言，合并排序优于插入排序，因为 NlgN < N2 但当输入大小较小时（例如 N=10），插入排序优于合并排序，主要是因为常量合并排序中的操作会增加它的执行时间。