如何计算时间复杂度

大家好，欢迎来到IT知识分享网。

啥是时间复杂度？

时间复杂度（$Timecomplexity$）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数. 时间复杂度常用大$O$表述，不包括这个函数的低阶项和首项系数。

个人理解为运行的次数

时间复杂度分类

• 算法完成工作最少需要多少基本操作叫做最优时间复杂度，是一种最乐观最理想的状态。
• 算法完成工作最多需要多少基本操作叫做最坏时间复杂度，是算法的一个保障。
• 算法完成工作平均需要多少基本操作叫做平均时间复杂度，它可以均匀全面的评价一个算法的好坏。

时间复杂度基本计算规则

• 基本操作即只有常数项，认为其时间复杂度为 $O(1)$
• 顺序结构，时间复杂度按加法进行计算
• 循环结构，时间复杂度按乘法进行计算
• 分支结构，时间复杂度取最大值
• 判断一个算法效率时，往往只需要关注操作数量的最高次项，其他次要项和常数项可以忽略
• 在没有特殊说明时，我们所分析的时间复杂度都是指最坏时间复杂度

时间复杂度的大小比较

$O(1)<O(lo{g}_{2}N)<O(N)<O(Nlo{g}_{2}N)<O(N^x)<O(2^N)<O(N!)$

时间复杂度的计算的时间复杂度计算

单重循环的时间复杂度计算

• $O(N)$

for(int i=1;i<=n;i++) 

一共运行了 $n$ 次

那时间复杂度就是$O(n)$

类似时间复杂度的还有

while(n--) 

• $O(lo{g}_{2}N)$

for(int i=1;i*i<=n;i*=2) 

提示

$i$	$1$	$2$	$4$	$\dots$
运行的次数	$0$	$1$	$2$	$\dots$

$n=2^{次数}$

一共运行了 $lo{g}_{2}n$ 次

那时间复杂度就是 $O(lo{g}_{2}n)$

双重循环的时间复杂度计算

计算双重循环的时间复杂度可以将内外两层循环的运行次数相乘

• $O(N^2)$

for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) } 

内层循环运行了 $n$ 次

外层循环也运行了 $n$ 次

一共运行了 $n^2$ 次

时间复杂度为 $O(n^2)$

• $O(NM)$

for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) } 

运行了 $nm$ 次

时间复杂度 $O(nm)$

• $O(Nlo{g}_{2}N)$

for(int i=1;i<=n;i++) { for(int j=1;j<=n;j*=2) } 

内层循环运行了 $lo{g}_{2}n$ 次

外层循环也运行了 $n$ 次

一共运行了 $nlo{g}_{2}n$ 次

时间复杂度为 $O(nlo{g}_{2}n)$

类似时间复杂度的还有

for(int i=1;i<=n;i++) { for(int j=1;j<=n;j+=i) } 

多重循环的时间复杂度计算

计算多重循环的时间复杂度可以将多层循环的运行次数相乘

• $O(N^3)$

for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int k=1;k<=n;k++) } } 

三层循环的时间复杂度各是 $O(n)$

将三层时间复杂度相乘得到总时间复杂度为 $O(n^3)$