【算法与数据结构】5 常见的时间复杂度,你知道吗?

简介: 【算法与数据结构】5 常见的时间复杂度,你知道吗?

一、前情回顾

👉传送门:1 详解线性查找法

👉传送门:2 线性查找的优化

👉传送门:3 线性查找的测试

👉传送门:4 循环不变量与复杂度分析

二、常见的时间复杂度

1.常见的时间复杂度

1.1 O ( n ) O(n)O(n)级别

✳️以线性查找法为例,对一个规模为n的数组做了一遍循环,时间复杂度叫做O(n)级别的


public static <E> int search(E[] data, E target){

for(int i = 0; i < data.length; i ++)

 if(data[i].equals(target))

  return i;

return -1;

   }

1

2

3

4

5

6

1.2 O ( n 2 ) O(n^2)O(n

2

)级别

❓提问: 一个数组中的元素可以组成哪些数据对?

for(int i = 0; i < data.length; i ++)

for(int j = i + 1; j < data.length; j ++)

 //获得一个数据对(data[i],data[j])

1

2

3

🙋回答: 使用双重循环来遍历这个数组,这个算法的时间复杂度是O ( n 2 ) O(n^2)O(n

2

)级别的


*️⃣虽然是O ( n 2 ) O(n^2)O(n

2

)级别的,但是这两重循环总共的执行的次数并不是n 2 n^2n

2

那么多次,差不多是n 2 / 2 n^2/2n

2

/2这么多次

每次j是从i+1开始的,遍历的数据对的i一定是小于j的,因为我们对于数据对的设计,认为(data[i],data[j])与(data[j],data[i])是一样的,所以大概扔掉了一半这样的数据对

✅但是对于这个算法,依然说它是O ( n 2 ) O(n^2)O(n

2

)级别的,因为前面的1/2它也是常数,对于算法复杂度的分析来说常数不重要


1.3 🚩复杂度分析,定要明确n是什么

❓提问: 遍历⼀个n ∗ n n*nn∗n 的⼆维数组

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

for(int j = 0; j < n; j ++)

 // 遍历到 A[i][j]

1

2

3

⬆️这二维数组的两个维度,两个维度都为n,从这样的一个视角看,算法的时间复杂度是O ( n 2 ) O(n^2)O(n

2

)级别的


⬇️假如是一个a ∗ a a*aa∗a的二维数组,且a ∗ a = n a*a=na∗a=n,这个二维数组的维度变成了a,这个二维数组中的元素总个数是n


for(int i = 0; i < a; i ++)

for(int j = 0; j < a; j ++)

 // 遍历到 A[i][j]

1

2

3

➡️对于这个算法复杂度来说,实际上它是一个O ( a 2 ) O(a^2)O(a

2

)级别的算法,因为这个二位数组的维度变成了a,如果要使用n来表示的话,这个算法的时间复杂度就是O ( n ) O(n)O(n)级别的(因为a ∗ a = n a*a=na∗a=n)


✴️同样是一个二维循环,一个是O ( n 2 ) O(n^2)O(n

2

)级别的,一个是O ( n ) O(n)O(n)级别的——因为 n代表的意思不一样,前者的n表示的是这个二位数组的某一个维度是n,后者的n表示的是二维数组的元素总数为n


1.4 O ( l o g n ) O(log n)O(logn)级别

❓提问: 求某一个十进制数字n所对应的二进制的位数是多少

while(n){

n % 2; // n 的⼆进制中的⼀位

n /= 2;

}

//每一次n % 2的的操作的结果都是0或者是1,

//这就是n的二进制的某一位

1

2

3

4

5

6

⌛️时间复杂度: 这个算法的时间复杂度是O ( l o g n ) O(log n)O(logn)级别,更严谨的说,对于当前这个算法应该是O ( l o g 2 n ) O(log_2 n)O(log

2

n),因为n每次都是除以2,相当于看这个数字n能够被多少次除以2之后结果等于0

如果给一个数字n,求这个数字n所对应的十进制的表示的那个位数——比如16这个数所对应的十进制的表示就是1和6,如何可以求出来?求十进制的某一位,应该是n对10求余数,然后n除以10——这个算法的时间复杂度应该是O ( l o g 10 n ) O(log_{10} n)O(log

10

n)


✴️不管是O ( l o g 2 n ) O(log_2 n)O(log

2

n)还是O ( l o g 10 n ) O(log_{10} n)O(log

10

n),或者是任意一个底数,通常管它叫做O ( l o g n ) O(log n)O(logn)级别的算法——省略掉底数是因为对于l o g loglog函数来说,不同的底数之间其实相差的只是一个常数而已

简单的使用换底公式做一下数学推导:

换底公式:

l o g a b = l o g c b l o g c a \boxed {log_a b = \frac{log_c b}{log_c a}}

log

a

b=

log

c

a

log

c

b

令a=2,b=n,c=10,代入换底公式

l o g 2 n = l o g 10 n l o g 10 2 log_2 n = \frac{log_{10} n}{log_{10} 2}

log

2

n=

log

10

2

log

10

n

💡很明显,l o g 2 n log_2 nlog

2

n与l o g 10 n log_{10} nlog

10

n之间就差了一个1 l o g 10 2 \frac{1}{log_{10} 2}

log

10

2

1

,和n没有关系,

✔️对于算法复杂度分析来说常数不重要,因此l o g 2 n log_2 nlog

2

n与l o g 10 n log_{10} nlog

10

n是同一个复杂度

✔️同理,l o g loglog以任何数为底,都是一个复杂度——叫做O ( l o g n ) O(log n)O(logn)级别的复杂度,也就是常说的对数复杂度


🚩看一个算法的复杂度,不能简单的去数循环的个数

比如下面⬇️这个循环也是一重循环,并不是O ( n ) O(n)O(n)级别的复杂度,因为在这重循环中n每次都是在除以2,并非如同每次减1一个一个的减到0,而是每次除2直到0,是l o g n log nlogn的级别到达了0,因此不是O ( n ) O(n)O(n)级别的复杂度,而是O ( l o g n ) O(log n)O(logn)级别的复杂度

while(n){

n % 2; // n 的⼆进制中的⼀位

n /= 2;

}

1

2

3

4

1.5 O ( l o g n ) O(log \sqrt{n})O(log

n

)级别

❓提问: 求解数字n的所有的约数——所谓一个数字a是n的约数,代表n可以将a给整除


🙋方法1: 遍历从1到n中的每一个数,i可以被n整除的情况下,i是n的一个约数


✅这个算法是一个O ( n ) O(n)O(n)级别的算法,对于这个问题进行优化

☑️优化: 一个数字的约数总是成对出现的,比如对于数字10,2是10的一个约数,用10除以2得到了5,5肯定也是10的一个约数

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

if(n % i == 0)

// i 是 n 的⼀个约数

1

2

3

🙋方法2: 其实对于这个i来说,不需要遍历到≤n,当i ∗ i > n i*i>ni∗i>n的时候,就可以了

这种循环,循环的次数就少了很多

✅这个算法的时间复杂度是O ( l o g n ) O(log \sqrt{n})O(log

n

)

*️⃣因为遍历的次数是1 ~ n \sqrt{n}

n

,当i为n \sqrt{n}

n

的时候,就退出了循环

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

if(n % i == 0)

// i 和 n / i 是 n 的两个约数

//实际上还有`i == n / i`这种情况,这种特殊的情况只找到了一个约数

1

2

3

4

1.6 指数级别的复杂度O ( 2 n ) O(2^n)O(2

n

)

❓提问: 求出长度为n的所有二进制数字,如长度为3的二进制数字共有8个,分别是0~7


✅这个算法的时间复杂度是O ( 2 n ) O(2^n)O(2

n

),


*️⃣因为长度为n,相当于共有n个位置,每个位置填0或1,整体就是2 n 2^n2

n

个情况

1.7 阶乘级别的复杂度O ( n ! ) O(n!)O(n!)

❓提问: 求一个长度为n的数组的所有排列


✅用到了数学中的全排列公式,时间复杂度是O ( n ! ) O(n!)O(n!)


因为所有的排列的个数就是n ! n!n!

1.8 常数级别的复杂度O ( 1 ) O(1)O(1)

❓提问: 判断一个数字n是否是偶数

return n % 2 == 0

//没有余数它就是一个偶数

1

2

✅这个算法的时间复杂度是O ( 1 ) O(1)O(1),因为不管n有多大,只需要执行一个指令/判断,就能判断出它是否是偶数,这个算法和n的具体的大小无关

即使这个算法要执行10条指令,如果我们这个算法要执行10条指令,那么它也是一个O ( 1 ) O(1)O(1)级别的算法,因为执行的指令的个数与n的大小无关,它还是一个常数

1.9 常见时间复杂度的比较

O ( 1 ) < O ( l o g n ) < O ( l o g n ) < O ( n ) < O ( n l o g n ) < O ( n 2 ) < O ( 2 n ) < O ( n ! ) O(1)<O(log n)<O(log \sqrt{n})<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)O(1)<O(logn)<O(log

n

)<O(n)<O(nlogn)<O(n

2

)<O(2

n

)<O(n!)


2.空间复杂度

和时间复杂度完全是同理的,对于一个算法而言,需要开辟的额外的空间的大小和数据规模n之间的关系是怎样的?


✳️以线性查找为例,并没有开任何额外的空间,因此算法的空间复杂度就是O ( 1 ) O(1)O(1)级别的


public static <E> int search(E[] data, E target){

for(int i = 0; i < data.length; i ++)

 if(data[i].equals(target))

  return i;

return -1;

   }

1

2

3

4

5

6

✅通常来讲,在算法设计的过程中,不太强调空间复杂度,现在计算机内存越来越大,相较而言时间是更值钱的,很多算法设计的核心思想是用空间换时间


相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
69 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1月前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
26 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
1月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
32 4
|
1月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
20 0
数据结构与算法学习十四:常用排序算法总结和对比
|
1月前
|
算法
[数据结构] -- 时间复杂度和空间复杂度
[数据结构] -- 时间复杂度和空间复杂度
15 0
|
1月前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
1月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
20 0
|
17天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
91 9
|
8天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
16 1