关于时间和空间复杂度的小问题

安然之风发布于 2011-09-03 18:55， 636 次点击

一个求两个整数的最大公因数的算法，怎么分析其时间和空间复杂度？
毛孩不懂！请各位指点迷津！！

5 回复

QQ3469571352011-09-03 21:20

你的代码呢，根据代码分析的，数据结构第一章就讲了；好好看书吧，数据结构很重要哦~

安然之风2011-09-04 11:45

回复 2楼 QQ346957135

代码：
while(b != 0)
{
    int t;
    t=a%b;
    a=b;
    b=t;
}

a , b 都是要输入的，但在不知道的情况下怎么去分析呢？我就是郁闷在这里。

QQ3469571352011-09-04 19:51

这只有一个循环，时间复杂度为线性阶，T（n）=O（n）；空间复杂度就是本段代码所有变量需要的存储空间，你数数就知道了。
时间复杂度，还有常量阶，平方阶，对数阶，指数阶等，一般用O（f(n)）表示，仔细看书吧，书上有例子的。

编程的乐趣2011-09-05 20:54

呵呵