算法之算法概述

一、算法概述

1、算法和数据结构

（1）什么是算法？

算法（algorithm）。在数学领域中，算法是用与解决某一类问题的公式和思想。在计算机科学领域中，算法是一系列程序指令，用于解决特定的运算和逻辑问题。从宏观上来看，数学和计算机领域的算法有很多相通之处。
衡量算法的重要标准：时间复杂度、空间复杂度
算法的应用场景：运算、查找、排序、最优决策
算法一方面可以检验程序员对计算机底层知识的了解，另一方面也可以衡量程序员的逻辑思维能力

（2）什么是数据结构？

数据结构（data structure），是数据的组织、管理和存储格式，其目的是为了高效地访问和修改数据。

线性结构：线性结构是最简单的数据结构，包括数组、链表、栈、队列、哈希表。

树：树是相对复杂的数据结构，其中比较有代表性的是二叉树，由它衍生除了二叉堆之类的数据结构

图：图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。

除了上述所列的集中基本数据结构以外，还有一些其他各式各样的数据结构。它们由基本数据结构变形拓展而来，用于解决某些特定问题，如跳表、哈希链表、位图等。

不同的问题会选用不同的数据结构

• 排序算法中的堆排序，利用的就是二叉堆这样一种数据结构
• 缓存淘汰算法LRU（Least Recently Used）最少使用，利用的就是特殊数据结构哈希链表。

2、时间复杂度

（1）执行次数

以下思想适用于基本操作执行次数的统计

场景一：线性

小明参加跑步比赛，以每秒10m的速度跑，那么跑完100米需要多久？

答案是10秒，如果100米换为 n 米呢？此时需要 n/10 秒。
可以记作T(n) = 0.1n，n为跑道长度。

场景二：对数

小红参加跑步比赛，每分钟跑总长度的一半，一个长度为2048米的跑道，第一分钟跑了1024米，第二分钟跑了512米，第三分钟跑了256米…那么跑的只剩1米需要几分钟？

这个问题的数学表达式是2048不断的除以2，除到剩余1用了几次。
log2048 = 11 。 那么小红跑完需要11分钟。可以记作 T(n) = logn。

场景三：常量

顾名思义，常量和变量 n 无关，不管n怎么变，执行次数始终是一个常量。记作T(n) = 2。

场景四：多项式

闪电侠参加跑步比赛，第一分钟跑了1千米，第二分钟跑了2千米，第三分钟跑了3千米跑的越来越快，每分钟内跑的千米数和第分钟数一致。那么跑10分钟，能跑多少米？

1+2+3+4+···+10 = 55千米
如果跑了n分钟呢？
1+2+···+(n-1)+n = (1+n)×n/2 = 0.5n²+0.5n （千米）
记作T(n) = 0.5n²+0.5n

（2）渐进时间复杂度

有了基本操作执行次数的函数T(n)还是不能分析和比较代码的运行时间。例如A的次数为T(n) = 100n,B的次数为T(n) = 5n² 。如果n的值不确定，还是无法确定A和B哪个算法的执行效率更高。为了解决时间分析的难题，有了渐进时间复杂度。

渐进时间复杂度：（asymptotic time complexity），若存在函数f(n)，使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常量，则将f(n)称为T(n)的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。也称作大O表示法

如何推导出时间复杂度？

• 如果运行时间是常数量级，则用常数1表示
• 只保留时间函数的*项
• 如果最高阶项存在，则省去最高阶项前面的系数。

例如：

• 场景一：T(n) = 0.1n，最高阶系数为0.1，省去0.1转化为时间复杂度 T(n) = O(n)
• 场景二：T(n) = logn，最高阶系数为1，转化为时间复杂度 T(n) = O(logn)
• 场景三：T(n) = 2，常数量级用常数1表示，转化为时间复杂度 T(n) = O(1)
• 场景四：T(n) = 0.5n²+0.5n，最高阶项为0.5n²，省去系数0.5，转化为时间复杂度 T(n) = O(n²)

这四种时间复杂度谁的执行用时更长？当n取足够大的值时，可以得出以下结论

• O(1) < O(logn) < O(n) < O(n²)

3、空间复杂度

空间复杂度（space complexity）。和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用了大O表示法。记作S(n)=O(f(n))，其中n为问题的规模，f(n)为算法所占存储空间的函数。

（1）空间复杂度的计算

常量空间

当算法的存储空间大小固定，和输入参数没有直接的关系时，空间复杂度记作O(1)。

void method1(int n){
	int temp = 3;
	...
}

线性空间

当算法分配的空间是一个线性空间的集合(如数组)，并且集合的大小和输入参数大小n成正比时，空间复杂度记作O(n)。

void method2(int n){
	int[] arr = new int[n];
	...
}

二维空间

当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入参数n成正比，空间复杂度记作O(n²)。

void method3(int n){
	int[][] matrix = new int[n][n];
	...
}

递归空间

递归是一个比较特殊的场景。虽然递归代码中并没有声明变量或者集合，但是在计算机执行程序时，会专门分配一块内存来存储“方法调用栈”（进栈、出栈）。

void method4(int n){
	if(n<=1){
		return;
	}
	method4(n-1);
	...
}

由此可见，递归的空间复杂度和递归的深度n成正比，那么递归的空间复杂度就是O(n)。

（2）、时间与空间的取舍

计算机的运算速度和资源是有限的。面对庞大而复杂的数据和业务场景，我们要选用最有效的利用方式。例如双重循环的时间复杂度是O(n²)，空间复杂度是O(1)，这属于牺牲时间换取空间。字典法的空间复杂度是O(n)，时间复杂度是O(n)，这属于牺牲空间来换取时间。在绝大多数时候，时间复杂度更为重要一些，我们能可多分配一些内存空间，也要提升程序的执行速度。

4、小结

• 什么是算法
  在计算机领域中，算法是一系列程序指令，用域处理特定的运算和逻辑问题。
  衡量算法优劣的标准有时间复杂度和空间复杂度。
• 什么是数据结构
  数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。
  数据结构包含数组、链表这样地线性数据结构，也包含树、图这种复杂地数据结构。
• 什么是时间复杂度
  时间复杂度是对一个算法运行时间长短地度量，用大O表示，记作T(n)=O(f(n))。
  常见地时间复杂度从低到高顺序，O(1) < O(logn) < O(n) < O(nlogn) < O(n²)
• 什么是空间复杂度
  空间复杂度是对一个算法在运行过程中临时占用内存空间大小的度量，用大O表示，记作S(n)=O(f(n))。
  常见的空间复杂度从低到高的顺序，O(1) < O(n) < O(n²)。其中递归算法的空间复杂度和递归深度成正比，记作O(n)。

本文地址：https://blog.csdn.net/weixin_44692700/article/details/107445959