算法复杂度

1、数据结构的概念

1.1何为数据结构？

将大量杂乱无章的数据通过某种结构进行管理。（增加、删除、查找、修改）数据。

1.2何为算法？

简单来说就是通过一系列的计算步骤，将输入的数据转化成预期中的结果。好的算法能够高效的管理数据。因此数据结构与算法不分家。

1.3如何学好数据结构与算法？

2、算法效率

2.1如何衡量一个算法的好坏？

一般是从时间和空间这两个维度来衡量。即时间复杂度与空间复杂度。一个算法运行时所需的时间越短，额外申请的空间越小，那么该算法就越好。
在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注算法的空间复杂度，更关注时间复杂度。（但在笔试与面试中两者都有所考察）

3、时间复杂度

3.1时间复杂度的定义

在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它是用来衡量程序运行的快慢。那为什么不直接去计算程序的运行时间呢？

1. 因为程序运行时间与编译环境（Debug版本下会加载调试信息，运行的较慢；Release版本下不会加载调试信息，运行的较快。）和运⾏机器的配置都有关系。比如同⼀个算法程序，用一个旧编译器进行编译和新编译器编译，在同样机器下运⾏时间不同。
2. 同⼀个算法程序，⽤⼀个低配置机器和⾼配置机器，运⾏时间也不同。
3. 并且程序的运行时间无法在程序写好之前确定

#include<stdio.h>
#include<time.h>
int main()
{
	int count = 0;
	int begin = clock();//clock函数是用来求程序运行到这行代码时花费的时间。(单位是毫秒)需要包含的头文件是<time.h>
	for (int i = 0; i < 1000000000; i++)
	{
		count++;
	}
	int end = clock();
	printf("该算法的运行时间为%d\n", end - begin);
	return 0;
}

3.2探讨时间复杂度的函数式T(N)

3.3案例

实际中，我们计算的也不是程序的精确执行次数，计算这个比较复杂，（不同的一句代码经过编译后，生成的二进制指令条数也不一样），也没有必要计算。对于T（N）而言，当N不断变大时，低阶项对高阶项的影响越来越小，因此我们只需要计算程序的大致执行次数。

3.4大O的渐进表示方法

大O符号（Big O notation）：是用于描述函数渐进⾏为的数学符号。

a.示例一

b.示例二

c.示例三

d.示例四

e.示例五

f.示例六

补充

g.示例七

4、空间复杂度

4.1空间复杂度的介绍

空间复杂度也是一个数学表达式，它是用来计算程序运行时额外申请的空间个数。空间复杂度不是计算程序占用了多少字节的空间，因为常规情况下，每个对象大小差异不会很⼤。

空间复杂度计算规则基本跟时间复杂度类似，也使⽤大O渐进表示法。

函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要由函数在运行时额外申请的空间个数来确定。

4.2空间复杂度的计算示例

a.示例1

b.示例2

c.示例3

4.3常见复杂度的对比

六、复杂度算法题

第一种算法

第二种算法

相较于第一种算法而言，这种算法相当于用空间换时间。