关于时间和空间复杂度的小问题 - 数据结构与算法

编程论坛 → 开发语言 → 『数据结构与算法』 → 关于时间和空间复杂度的小问题

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

只看楼主

安然之风

等　级：论坛游民
帖　子：43
专家分：23
注　册：2011-1-6
结帖率：63.64%

已结贴√ 问题点数：20 回复次数：5

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

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

搜索更多相关主题的帖子: 空间　公因数　

2011-09-03 18:55

QQ346957135

等　级：黑侠
帖　子：148
专家分：658
注　册：2011-8-9

得分:10

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

A real warrior never quits.

2011-09-03 21:20

安然之风

等　级：论坛游民
帖　子：43
专家分：23
注　册：2011-1-6

得分:0

回复 2楼 QQ346957135

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

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

2011-09-04 11:45

QQ346957135

等　级：黑侠
帖　子：148
专家分：658
注　册：2011-8-9

得分:0

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

A real warrior never quits.

2011-09-04 19:51

编程的乐趣

等　级：蜘蛛侠
威　望：1
帖　子：229
专家分：1027
注　册：2011-4-4

得分:10

呵呵

2011-09-05 20:54