视频地址:009复杂度04时间复杂度的估算_哔哩哔哩_bilibili
我这里准备了几个东西，我直接拷过来，因为这些东西没必要，我敲我就直接拿过来。好，我们来看一下我这里写了很多个这个方法，我们来看一下这些方法它的时间复杂度是多少，我们看一下它的时间复杂度是多少？那怎么算这个时间复杂度刚刚已经说得非常清楚了，其实就是估算一下这个程序指令的执行次数，我们看一下这个，同学们看这个你觉得这个需要执行多少条指令呢？
我们来算一下，这里需要执行多少条？三条吗？大概是多少条？这个判断我们就不管啊，这个看起来是三条，其实是一条，是吧？判断我们不管啊这个判断我们不管，为什么呢？你看这一条跟这一条跟这一条其实只可能会执行其中的一条，所以这里我们假定是一那你可能会说老师你这个不严谨，为什么这两条不算呢？
其实这两条算不算对我们后面真的没有影响这个这个问题，我们等会会讲到，我们先不算它好吧？
那么再看这个，那这个是一条，这个一开始会执行一句这个对吧？一然后a加加呢它会执行多少次？注意我这里是4，我这里是4，说a加加他肯定会执行4次，然后这个判断呢应该也是4次，然后里面这个东西呢我们也是4次，对不对？好，大概就是这样子。
好，那这个总的算下来是多少条呢？我们来算一下啊。4+42，再加42对吧？12+2那就是14，好，我们就假定它是14，我们再看看这个这个这个是多少次啊？首先这个是一对吧，然后我们注意这个是I小于n所以这个判断会判断n次，AA加加也会执行n次要，这个也会执行n次，所以相当于就是三n对吧？
再看这个这个大概会执行多少次的，这个大概会执行多少次的？
首先这个I一次对不对？然后这个这个n次，这个呢这个也是n次，所以这已经是二n了对吧？然后里面呢想想里面整个货循环是不会执行n次啊，对不对？里面整个货循环会执行n次对不对？所以应该是n乘以它里面有多少次？那它里面又有什么东西呢？它里面有个勾，勾的话应该是114，然后这个会执行n次，然后这个会执行n次，然后这个会执行n次，相当于是这个是三，应该是这样算。
应该是这样算对不对？好，那这样算下来那大概是多少？1+2n加这个是然后这个是三n平方，好，n平方我就写成这样。
好，那这个算下来其实就是三n平方加三n对吧？然后加一，大概来说就是这样子。
好，那我们再看一下这个这个呢这个打算呢这个也差不多嘛，对吧？首首先这个只会执行一次，对不对？只是一次，然后这个呢n次判断对吧？然后这个呢这个也是n次，那我们就可以这样子呃n对吧？然后里面又是n好，那里面多少次呢？首先我们这个这个初始化语句一次，然后这个判断呢注意我这里是15，我这里是15不是n啊，那15次那这里是15次，所以这两个加起来就是30，然后这个这里又有15，那应该是45，对吧？
那这里呢就是46，那这样算下来其实就是48n加1，大概来说就是这样子对吧？我只能说大概来说是这样子，那我们再看一下这个这个这个都知道这样子啊，凡是这个外循环你这个判断这个判断我们就不算了，好吧？
这个这个我们就不算了，我们就看他这个执行多少次，我们就关注一下他执行多少次，大家这个能看懂吗？那像这种你觉得这个需要执行多少次呢？这个是什么意思啊？这个代码看起来就有点复杂啊，是吧？你看这个其实在干什么？这个其实是每次都是先n除以2，要复制给n相当于就是看一下n除以2的结果是否大于0，是否大于0，对吧？
如果这个除以2还大于0，那就执行一次，那接下来呢怎么样？再除以2。如果还大于0再执行一次，那接下来再除以2还大于0再执行一次，相当于就是这个n如果能除多少次二这个就能执行多少次，是不是这个意思？听我这个解释是不是n能除以多少次二，这个这个值就执行多少次，是不是这意思啊？
好，那比如说举个例子，你这个n是8，假设你这个n是8，第一次除等于4，第二次除等于2，第三次除一，那接下来如果你还除，那就变成0，就不符合条件，所以前面三次是符合的，所以你执行了三次，你执行了三次，那你相当于就是2的三次方，其实就是8，相当于就是看一下这个是多少。
嗯16其实是2的4次方，所以如果你传的是16，它执行的是4次，我这样解释大家能不能听懂？
其实就是求这个，其实就是求这个，那这个其实是什么东西呢？怎么求出这个4呢？怎么求出这个4啊？四，如果你学过数学的话，其实就是log26，对不对？然后这个3其实就是取这个8这个对数，相当于就是我们最后这个执行次数其实就是log二n你n传什么？我就对二取对数要算出来，对吧？所以最后的执行次数同学们我们算出来了，其实就是等于这个大家能不能接受？
应该是没问题的，对吧？这是最基本的一个运算嘛，这个没什么问题啊，再看看这个啊这个我们现在就马上能猜出来了，log5看一下这个n能除以5除多少次，对吧？那这个马上就可以算出来。
噢这个同学非常简单，是吧？好，那我们看一下这个那这个事实这个有多少次了？那这个看起来就很恐怖了，这个老师你看这里我不一样噢，I加等于I I加等于I噢这不是I加加噢，注意看清楚，那这个怎么算？这个怎么算？
大家看这样啊，我们先把里面这个算出来，里面这个其实很简单，一次对不对？然后这个这个你从0开始要小于n那肯定是n次嘛，那这里是n次吧，这也是n次嘛，所以你可以认为是1+3n对吧？这是里面的。
那外面这个它会支撑多少次？这个I加I加等于II加等于I7是等价s吗？其实等价于I乘以二。大家先思考I加等于I其实是不是I等于I乘以2，I乘以2不就是两个I相加吗？大家能不能听懂？是不是等于这个对吧？所以这个会执行多少次呢？还是一样的问题。
就看这个I每次都乘以二，每次都乘以二，什么时候会超过这个n对吧？所以这里其实同学们我跟你直接跟你说吧，其实还是log二n还是log二n这里肯定还是这个，当然我这里应该是写错了，这应该是要一从一开始，所以是要从一开始，这是一啊，同学们注意啊，这是一一开始一开始就不会了，对吧？
你看乘以2，然后再乘以2×2，那就看你这个2呢要乘多少次能达到n就是二。就是对吧？你本来是1×2再×2再乘以2，你每次都是×2吧，那你这个2乘多少次呢？那不是看二的多少次方是n吗？那你这个多少次那不不是又是log n吗？对不对？又是logo二维码是吧？所以里面的这个执行多少次呢？执行logo二n次，log二n次就这么简单同志们好。
那这样的话这样就是 log 2n乘以里面的1+3n对不对？然后外面的这个是一次啊，这个是一次，对不对？好，那这个是什么？这个是log二n次，这个也是log二n次，对不对？所以你可以认为是2乘以那个啊噢n次。好，就是这样子好。那这样算下来是多少呢？算下来的话应该是三乘以 log二n加上3乘以什么？N log二n好，大概就是这样子，同学们最终算下来大概就是这样子，好吧？
原理与使用细节)