三道计算时间复杂度的题目
date
Nov 16, 2022
slug
time-complex
status
Published
tags
算法
summary
等比数列通项公式
type
Post
出处： 算法第四版 Edition Sedgewick 著，问题 1.4.7
三道小题初看觉得很简单，但是仔细一分析，a、b小题里面的内循环操作次数是和外层的n、i值有关，并不是简单的操作N次，很久没有算过时间复杂度了，稍微感到有点棘手。
我们写代码跑一下看看运行次数。
从直觉上来说a和b的操作次数是差不多的，但是实际代码运行两者差别很大
答案和做法
a小题
如果按照通常的方法，分析for有多少个，那么分析起来会很痛苦，外层循环是的操作很容易看出来，但是第二个for，i和n是挂钩的，这个时候通常的方法就不起作用了。
换一种思路，先写一下
sum++操作的运行次数，可以得到N N/2 N/4 ... 1 ，这实际上是一个等比为2的等比数列，我们把这个数列记为L，它的项数为n。注意到第n项等于1，而L的首项是N，那么，得出对
L用等比公式求和，，把n带入，化简即可得到也就是说内循环的总操作次数是2N，那么它其实就是级别的算法
b小题
b小题其实和a小题很相似，只不过b的数列变为
1 2 4 ... N，等比为2，同样是n项，n同样等于，因为，而L的和，那么b也是级别的算法c小题
c小题用常规的做法做即可，c是级别的算法
解释一下a，b同为O(N)级别的算法，为什么它们实际操作次数却不一样，因为O(N)取的是近似值，剩余的较低次项都被忽略了，但是实际计算中低次项的次数同样很关键，因此a，b的执行次数会不一样