计算 运行-循环时间
Calculating a Run-Time of a loop
我试图在 O(n^2) 时间内证明以下算法 运行s。
我得到了代码：
主要是伪代码
function generalFunction(value)
for(i=1 to value.length-1)// value is an array, and this runs `n-1 Times`
for(j=1 to value.length-i // This runs `n-1(n-1)` times?
if value[j-1] > value[j] //This runs n^2 times?
swap A[j+1] and value[j] //How would would this run?
第一行，我计算了运行s n-1次。因为循环进行了 n 次，但是由于我们从 arbritray 数组的长度中减去 1，所以它将是 n-1 次（我相信）。
第二行也可以这样说，只是我们必须将它乘以原始的 for 循环。
但是，我不确定最后两行，第三行会运行 n^2 次吗？由于两个嵌套循环，我只写了 n^2。我也不确定如何接近最后一行，任何输入都将不胜感激。
是的，这将 运行 in n^2 - 根据您的评论。请注意，内部 if 语句（swap）的执行与双循环 运行 n^2 次无关。此外，负一部分 (n-1) 仍然使它成为 n^2，因为您基本上是在寻找上限〜近似值〜，而 n^2 是最严格的界限。基本上 (n-1)(n-1) = n^2 - 2n +1 由 n^2 项支配。
有关与此类似的定义和可行示例，请参阅 Wikipedi - example section
P.S。 Bug O 是关于最坏情况的。所以在最坏的情况下，if 语句将始终为真，因此交换将命中每个循环周期。这意味着如果你设置一个断点，它将被击中 (n-1)*(n-1) 次。扩展这意味着 n^2 - 2n + 1 次。
我试图在 O(n^2) 时间内证明以下算法 运行s。
我得到了代码： 主要是伪代码
function generalFunction(value)
for(i=1 to value.length-1)// value is an array, and this runs `n-1 Times`
for(j=1 to value.length-i // This runs `n-1(n-1)` times?
if value[j-1] > value[j] //This runs n^2 times?
swap A[j+1] and value[j] //How would would this run?
第一行，我计算了运行s n-1次。因为循环进行了 n 次，但是由于我们从 arbritray 数组的长度中减去 1，所以它将是 n-1 次（我相信）。
第二行也可以这样说，只是我们必须将它乘以原始的 for 循环。
但是，我不确定最后两行，第三行会运行 n^2 次吗？由于两个嵌套循环，我只写了 n^2。我也不确定如何接近最后一行，任何输入都将不胜感激。
是的，这将 运行 in n^2 - 根据您的评论。请注意，内部 if 语句（swap）的执行与双循环 运行 n^2 次无关。此外，负一部分 (n-1) 仍然使它成为 n^2，因为您基本上是在寻找上限〜近似值〜，而 n^2 是最严格的界限。基本上 (n-1)(n-1) = n^2 - 2n +1 由 n^2 项支配。
有关与此类似的定义和可行示例，请参阅 Wikipedi - example section
P.S。 Bug O 是关于最坏情况的。所以在最坏的情况下，if 语句将始终为真，因此交换将命中每个循环周期。这意味着如果你设置一个断点，它将被击中 (n-1)*(n-1) 次。扩展这意味着 n^2 - 2n + 1 次。