辗转相除法的时间复杂度如何计算的为什么是 2long(n)

首页课程实战体系课手记专栏慕课教程

辗转相除法的时间复杂度如何计算的为什么是 2long(n)

来源：2-7 更多关于O(n^2)排序算法的思考

qq_飞羽醉月_0

2017-09-24

写回答

1回答

liuyubobobo

liuyubobobo

2017-09-24

已采纳

辗转相除法的时间复杂度是O(logn)级别的。这个严格的数学计算比较复杂，可以直观理解一下：辗转相除法每次将两个数中的一个和另一个数做除法，并且这个除数至少为2，所以两个数的大小在以指数级下降，最差下降为1。所以其时间复杂度是logn级别的。

0

1

qq_飞羽醉月_0

非常感谢！

2017-11-13

共1条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

归并排序的时间复杂度是如何计算得出的？

回答 1

原地归并排序是否可以算作是那个神秘的排序算法

回答 1

数组中第N大元素的问题，如果有重复怎么办？

回答 1

请问一路的快排的时空复杂度怎么计算呢？

回答 1

同样一个数组(拷贝的数组)两次排序，所用的时间为什么会不一样呢？(好像冒泡排序的优化，跟插入排序有些相似呢）

回答 1

打开慕课网App查看更多内容