采用以下插入排序算法：
我知道通过检查它很容易 O(n^2) 。但就证明它是 O(n^2) 而言，我将如何去做呢？我可以将所有操作相加，但n + "sum of j=2 to n"据我所知并不会真正导致 n^2。
我真的不知道如何准确地证明这一点。有人可以尝试清楚地解释我将如何以一种适用于 O(n^3) 算法的方式证明这一点吗？
问问题
2553 次
3 回答
2
通过考虑在最坏情况下执行了多少操作，您可以证明 O 复杂度很大。您已经完成了计数部分并在图像的右侧栏中输入了结果，因此还有待证明的是主导项是O(n^2)。
除了涉及总和的术语之外，您的程序还包含执行n-1时间的指令，因此这些都是O(n)术语。
现在是总和的条款。在最坏的情况下， at_j可能是j因为您最终可能会将i设置的 which一直递减j到 0。所以在最坏的情况下，我们有t_j = j一个带有 a 的术语，sum from 2 to n of j它是O(n^2)。这是由于遵循数学恒等式：
这可以通过将这些系列中的两个相加来证明，注意将两个相加的项相加n+1，然后将总和除以二。看看wolfram 中的证明。
最后，因为O((n^2 + n)/2) = O(n^2)您知道包含总和的项在运行时占主导地位，这就是算法的原因O(n^2)
于 2013-09-24T15:04:41.787 回答
2
这是 O(n^2) 因为你有一个乘法，而不是一个和。以逆序排列的数组为例：
10 9 8 7 6 5 4 3 2 1
在这些情况下，内部循环的每次迭代都将在插入下一个元素之前扫描并移动数组的整个排序子部分。这为插入排序提供了二次运行时间（即 O(n2)）。
理解复杂性的最好方法是尝试找到最坏的例子并遵循算法的步骤。
于 2013-09-24T03:30:11.727 回答
-2
假设 1：如果一个过程 P 运行不超过 T 次，并且 P 每次运行时间为 O(f(N))，那么总运行时间为 O(T*f(N))
假设 2：如果过程 P 在 O(f(N)) 时间内运行，而过程 Q 在 O(g(N)) 时间内运行，则运行 P 后跟 Q 需要 O(f(N) + g( N)) 时间。
为了迂腐，如果您愿意，假设 1 遵循假设 2。
假设 3：赋值和算术是 O(1) 操作。
结合这三个假设，你得到你的结果。
第 6 行和第 7 行分别以 O(1) 和 O(1) 时间运行，因此它们一起运行在 O(1 + 1) = O(1) 时间。（假设 3 和 2）
第 5 行确定 {6,7} 将运行不超过 A.Length - 0 次，因此 {5,6,7} 的运行时间为 O(A.Length * 1) = O(A.Length) (By假设 1)
第 2、4 和 8 行运行时间为 O(1)，因此 {2,4,5,6,7,8} 运行时间为 O(1 + 1 + A.Length + 1) = O(A.Length)时间。（再次通过假设 3 和 2）
第 1 行确定 {2..8} 将运行不超过 A.Length 次，因此行 {1..8} 的运行时间为 O(A.Length * A.Length) = O(A.Length ^2 ) （由假设 1）。
于 2013-09-24T03:30:47.357 回答