问题描述
我正在跟踪一个在线课程，我不明白如何估算一个算法的增长顺序这里是一个例子
I am following the an online course and I can't understand well how to estimate the order of growth of an algorithm here s an example
什么是订单以下代码片段
作为N的函数的最坏情况运行时间的增长？
What is the order of growth of the worst case running time of the following code fragmentas a function of N?
Int sum = 0;
For (int i = 1; i <= 4*N; i = i*4)
for (int j = 0; j < i; j++)
sum++;
任何人都可以向我解释如何获得
Can anyone explain to me how to get it
推荐答案
只需计算执行语句 sum ++; 的次数。
Just calculate how many times the statement sum++; is executed.
= 1 + 4 + 16 + 64 ... + 4 * N
= 1 + 4 + 16 + 64 ... + 4*N
这是一个几何级数，共同因子为4.如果这个数字系列是k，然后
This is a geometric progression with common factor of 4. If number of terms in this series is k, then
4^k = 4*N.
Sum of series = (4^k - 1)(4-1) = (4*N - 1)/3.
按照增长顺序，我们忽略不变因素。
In order of growth we neglect the constant factors.
因此，复杂度为O（N）。
Hence the complexity is O(N).
这篇关于估计算法运行时间的增长顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！