欧几里得算法求最大公约数正确性证明与时间复杂度分析


正确性证明

Portal


时间复杂度分析

  • 两数相除,余数必定严格小于除数,被除数不一定。
  • 我们可以发现两轮,a,b都各自缩小一半,直到递归结束(我们也不清楚),所以最坏时间复杂度为$O(log(a + b))$(得出结论不严谨,但是我们只需要记住结论即可)

评论
 Previous
Nowcoder 2020 Multi University Training Contest 5-I Nowcoder 2020 Multi University Training Contest 5-I
ProblemPortal Meanings在一个无限大的棋盘上,最大程度的摆放棋子H,要求棋子H相邻必须有G,E。 Thoughts我们可以发现一旦GE相邻,无论H在哪里,我们都会发现,无法符合题意。所以最优的方案就是让网格图中GE,
Next 
Nowcoder 2020 Multi University Training Contest 5-D Nowcoder 2020 Multi University Training Contest 5-D
ProblemPortal Notices Any number of consecutive Drop-2 operations is considered a multi-drop. 注意,这里是连续的操作一,都被看做一个muti d
  TOC