详解O(log n)时间复杂度的由来

详解O(log n)时间复杂度的由来

算法复杂度共分为两类:时间复杂度、空间复杂度

时间复杂度是指执行这个算法所需要的计算工作量时间;

空间复杂度是指执行这个算法所需要的内存空间。

一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度,也代表了时间复杂度O()。

一、O(log n)简单算法演示讲解

int a=1;

while(a

a=a*2;

}

时间复杂度就是看某个语句的最大执行次数:

int a=1 //执行了1次

while循环体的执行次数:与a的值有关系,a每次循环都要增大2倍,其值为:2、4、8、16……

假设x次循环后,a的值大于n了,那么关系就是2^x=n,推出循环体一共执行的次数为x=log2 ~n(底数为2,对数为n),即这个循环的时间复杂度为O(x)=O(log n)

相关推荐

注销账户会发生什么?
beat365在线体育访问不了

注销账户会发生什么?

📅 10-29 👁️ 7072
在星巴克兼职是一种怎样的体验?
beat365在线体育访问不了

在星巴克兼职是一种怎样的体验?

📅 08-07 👁️ 4541
深入解析IT专业分类、方向及就业前景:高考毕业生如何选择适合自己的IT专业?重点探索近年来人工智能专业发展及人才需求