算法-求余算法优化问题

Question

算法优化问题
现有算法如下:
while (b<>0)
b:=a%b
其中a,b为整数 a>b>0
算法复杂度为O(a^1/3) Ω(log a)
问题:
这个算法复杂度怎么计算出来的？
怎么优化这个算法让算法复杂度降低？

Answer 1

算法复杂度，主要由两个方面去衡量。即时间复杂度和空间复杂的。即所谓的时空问题。
你这个while语句热行的次数，叫时间频度。记为T(n)。你可以理解为循环的次数。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。
按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
同理：
降低算法的复杂度，也是从时间和空间上考虑。