【算法与数据结构】5 常见的时间复杂度，你知道吗？-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法与数据结构】5 常见的时间复杂度，你知道吗？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

欢迎来到爱书不爱输的程序猿的博客, 本博客致力于知识分享，与更多的人进行学习交流

本文收录于算法与数据结构体系专栏,本专栏对于0基础者极为友好,欢迎与我一起完成算法与数据结构的从0到1的跨越

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

一、前情回顾

👉传送门:1 详解线性查找法
👉传送门:2 线性查找的优化
👉传送门:3 线性查找的测试
👉传送门:4 循环不变量与复杂度分析

二、常见的时间复杂度

1.常见的时间复杂度

1.1 $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 $O(n^2)$ 级别

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

for(int i = 0; i < data.length; i ++)
	for(int j = i + 1; j < data.length; j ++)
		//获得一个数据对(data[i],data[j])

🙋回答： 使用双重循环来遍历这个数组，这个算法的时间复杂度是 $O(n^2)$ 级别的
- *️⃣虽然是 $O(n^2)$ 级别的，但是这两重循环总共的执行的次数并不是 $n^2$ 那么多次，差不多是 $n^2/2$ 这么多次
  - 每次j是从i+1开始的，遍历的数据对的i一定是小于j的，因为我们对于数据对的设计，认为(data[i],data[j])与(data[j],data[i])是一样的，所以大概扔掉了一半这样的数据对
✅但是对于这个算法，依然说它是 $O(n^2)$ 级别的，因为前面的1/2它也是常数，对于算法复杂度的分析来说常数不重要

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

❓提问： 遍历⼀个 $n * n$ 的⼆维数组

for(int i = 0; i < n; i ++)
	for(int j = 0; j < n; j ++)
		// 遍历到 A[i][j]

⬆️这二维数组的两个维度，两个维度都为n，从这样的一个视角看，算法的时间复杂度是 $O(n^2)$ 级别的
⬇️假如是一个 $a * a$ 的二维数组，且 $a * a = n$ ，这个二维数组的维度变成了a，这个二维数组中的元素总个数是n

for(int i = 0; i < a; i ++)
	for(int j = 0; j < a; j ++)
		// 遍历到 A[i][j]

➡️对于这个算法复杂度来说，实际上它是一个 $O(a^2)$ 级别的算法，因为这个二位数组的维度变成了a，如果要使用n来表示的话，这个算法的时间复杂度就是 $O (n)$ 级别的(因为 $a * a = n$ )
✴️同样是一个二维循环，一个是 $O(n^2)$ 级别的，一个是 $O (n)$ 级别的——因为 n代表的意思不一样，前者的n表示的是这个二位数组的某一个维度是n，后者的n表示的是二维数组的元素总数为n

1.4 $O (l o g n)$ 级别

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

while(n){
	n % 2; // n 的⼆进制中的⼀位
	n /= 2;
}
//每一次n % 2的的操作的结果都是0或者是1，
//这就是n的二进制的某一位

⌛️时间复杂度： 这个算法的时间复杂度是 $O (l o g n)$ 级别，更严谨的说，对于当前这个算法应该是 $O(log_2 n)$ ，因为n每次都是除以2，相当于看这个数字n能够被多少次除以2之后结果等于0

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

✴️不管是 $O(log_2 n)$ 还是 $O(log_{10} n)$ ，或者是任意一个底数，通常管它叫做 $O (l o g n)$ 级别的算法——省略掉底数是因为对于 $l o g$ 函数来说，不同的底数之间其实相差的只是一个常数而已

简单的使用换底公式做一下数学推导：
换底公式: $\boxed {log_a b = \frac{log_c b}{log_c a}}$
令a=2,b=n,c=10,代入换底公式 $log_2 n = \frac{log_{10} n}{log_{10} 2}$
💡很明显， $log_2 n$ 与 $log_{10} n$ 之间就差了一个 $\frac{1}{log_{10} 2}$ ，和n没有关系，
✔️对于算法复杂度分析来说常数不重要，因此 $log_2 n$ 与 $log_{10} n$ 是同一个复杂度
✔️同理， $l o g$ 以任何数为底，都是一个复杂度——叫做 $O (l o g n)$ 级别的复杂度，也就是常说的对数复杂度

🚩看一个算法的复杂度，不能简单的去数循环的个数
- 比如下面⬇️这个循环也是一重循环，并不是 $O (n)$ 级别的复杂度，因为在这重循环中n每次都是在除以2，并非如同每次减1一个一个的减到0，而是每次除2直到0，是 $l o g n$ 的级别到达了0，因此不是 $O (n)$ 级别的复杂度，而是 $O (l o g n)$ 级别的复杂度

while(n){
	n % 2; // n 的⼆进制中的⼀位
	n /= 2;
}

1.5 $\sqrt{n})$ 级别

❓提问： 求解数字n的所有的约数——所谓一个数字a是n的约数，代表n可以将a给整除
🙋方法1： 遍历从1到n中的每一个数，i可以被n整除的情况下，i是n的一个约数
- ✅这个算法是一个 $O (n)$ 级别的算法，对于这个问题进行优化
- ☑️优化： 一个数字的约数总是成对出现的，比如对于数字10，2是10的一个约数，用10除以2得到了5，5肯定也是10的一个约数

for(int i = 1; i <= n; i ++) 
	if(n % i == 0)
	// i 是 n 的⼀个约数

🙋方法2： 其实对于这个i来说，不需要遍历到≤n，当 $i * i > n$ 的时候，就可以了
- 这种循环，循环的次数就少了很多
- ✅这个算法的时间复杂度是 $\sqrt{n})$
  - *️⃣因为遍历的次数是1 ~ $\sqrt{n}$ ，当i为 $\sqrt{n}$ 的时候，就退出了循环

for(int i = 1; i * i <= n; i ++)
	if(n % i == 0)
	// i 和 n / i 是 n 的两个约数
	//实际上还有`i == n / i`这种情况，这种特殊的情况只找到了一个约数

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

❓提问： 求出长度为n的所有二进制数字，如长度为3的二进制数字共有8个，分别是0~7
✅这个算法的时间复杂度是 $O(2^n)$ ，
- *️⃣因为长度为n，相当于共有n个位置，每个位置填0或1，整体就是 $2^n$ 个情况

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

❓提问： 求一个长度为n的数组的所有排列
✅用到了数学中的全排列公式，时间复杂度是 $O (n!)$
- 因为所有的排列的个数就是 $n!$

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

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

return n % 2 == 0
//没有余数它就是一个偶数

✅这个算法的时间复杂度是 $O (1)$ ，因为不管n有多大，只需要执行一个指令/判断，就能判断出它是否是偶数，这个算法和n的具体的大小无关
- 即使这个算法要执行10条指令，如果我们这个算法要执行10条指令，那么它也是一个 $O (1)$ 级别的算法，因为执行的指令的个数与n的大小无关，它还是一个常数

1.9 常见时间复杂度的比较

$\sqrt{n})<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)$

2.空间复杂度

和时间复杂度完全是同理的，对于一个算法而言，需要开辟的额外的空间的大小和数据规模n之间的关系是怎样的？
✳️以线性查找为例，并没有开任何额外的空间，因此算法的空间复杂度就是 $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;
    }

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

【算法与数据结构】5 常见的时间复杂度，你知道吗？文章来源地址https://www.toymoban.com/news/detail-448517.html

到了这里，关于【算法与数据结构】5 常见的时间复杂度，你知道吗？的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

一、前情回顾

二、常见的时间复杂度

1.常见的时间复杂度

1.1 $O (n)$ 级别

1.2 $O(n^2)$ 级别

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

1.4 $O (l o g n)$ 级别

1.5 $\sqrt{n})$ 级别

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

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

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

1.9 常见时间复杂度的比较

2.空间复杂度

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

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

一、前情回顾

二、常见的时间复杂度

1.常见的时间复杂度

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

1.2 O ( n 2 ) O(n^2) O(n2)级别

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

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

1.5 O ( l o g n ) O(log \sqrt{n}) O(logn ​)级别

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

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

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

1.9 常见时间复杂度的比较

2.空间复杂度

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

1.1 $O (n)$ 级别

1.2 $O(n^2)$ 级别

1.4 $O (l o g n)$ 级别

1.5 $\sqrt{n})$ 级别

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

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

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