数据结构第一关---- 复杂度

初阶数据结构第一关---- 复杂度

什么是数据结构？

我们之前已经学习过数组相关的概念，这里举个例子：

int a=10;
//我们需要定义1000个整型变量数组
int arr[1000];
//如果我们要进行更改的话，可以这样做
int arr[i]=100;
1
2
3
4
5

同理，数据结构就是对数据进行管理。

概念：数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数 据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤，所以我们要学各式各样的数据结构， 如：线性表、树、图、哈希等

算法的概念：算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为 输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果。

数据结构好比是一个收纳整齐的容器，算法好比是取得想要东西的统筹方法，所以说数据结构和算法不分家

引入一个例子：如何衡量算法好坏

轮换数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
1
2
3
4
5
6

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
1
2
3
4
5

思路：

循环K次将数组所有元素向后移动⼀位

分析的过程：

在OJ平台上提交的情况如下：

这就引出了如何衡量算法的好坏呢？

从复杂度的角度来看，复杂度从空间和时间两个维度来看。

复杂度

算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好 坏，⼀般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。 在计算 机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发 展，计 算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂 度。

（题外话：根据摩尔定律，计算机每过16-24年性能翻一番）

时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时 间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？

1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译 器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。

2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。

3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

以下是测试时间的代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <time.h>
int main()
{
	//计算程序运行时间
	int begin = clock();
	int count = 0;
	for (int i = 0; i < 10000; i++)
	{
		count++;
	}
	int end =clock() ;
	printf("time:%d\n", end - begin);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

计算公式：

我们可以不用考虑每条语句运行时间，只看运行次数

因为程序时间效率和运行次数成正比

那么算法的时间复杂度是⼀个函数式T(N)到底是什么呢？这个T(N)函数式计算了程序的执⾏次数。通 过c语⾔编译链接章节学习，我们知道算法程序被编译后⽣成⼆进制指令，程序运⾏，就是cpu执⾏这 些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)，假设每 句指令执⾏时间基本⼀样(实际中有差别，但是微乎其微)，那么执⾏次数和运⾏时间就是等⽐正相关， 这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的 算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率⼀定优于算法b.

下面来看一道例题：

// 请计算⼀下Func1中++count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

一些疑问：

为什么声明变量的时候不进行考虑呢？

因为声明的时候，执行次数为1，实在是太小了，可以忽略不计，上面写的可以测试运行时间的代码里面，10000次可能运行时间都为0，所以声明的时候可以忽略不记

---

实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很 ⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执⾏次数意义也不⼤， 因为我么计算时间复杂度只是想⽐较算法程序的增⻓量级，也就是当N不断变⼤时T(N)的差别，上⾯我 们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩，所以我们只需要计算程序能代表增⻓量 级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

⼤O的渐进表⽰法

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