您当前的位置： 首页 > 学无止境 > 心得笔记 网站首页心得笔记
一个视频教会你算法的时间复杂度
发布时间：2020-10-07 15:46:19编辑：雪饮阅读（）
时间复杂度及表示法
算法的时间复杂度用大O表示法。
下面将以python语法示例
O(n)示例：
def test(num);
total = 0
for i in range(num);
total+=i
retuen total
因为这里total=0是常数，而total+=i被执行num次，即那么total+=i可以看作b，num可以看作n，即是nb，所以就是O(n).
O(1)示例：
def o1(num);
i = num
j = num*2
return i+j
因为这里不存在循环，都是常数，所以就算O(1)
O(logN)示例：
def oLogN(num);
i = 1
while (i<num);
i = i*2
return i
因为这里i终止的条件是i*2*2*2…,那么就是要求i乘以多个2，即2的多少次方，所以这里就是log n
O(m+n)示例：
def OMN(num1,num2);
total = 0
for i in range(num1);
total +=i
for j in range(num2);
total +=j
return total
这个就很简单了，两个for循环而已
O(nlogn)示例：
def ONLOGN(num1,num2);
total = 0
j = 0
for i in range(num1);
while(j < num2);
total += i + j
j = j * 2
return total
这个结合上面O(n)和O(logn)也就不难理解了。
O(n2)示例：
def ON2(num);
total = 0
for i in range(num);
for j in range(num);
total += i + j
return total
这个结合上面O(n)也就不难理解了。
时间复杂度对比：
关键字词：算法,时间复杂度
上一篇：8-1 常见算法考察点
下一篇：一个视频教会你算法的空间复杂度