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

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

什么是数据结构？

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

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

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

概念：数据结构(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]

示例 2:

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

思路：

循环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;
}

计算公式：

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

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

那么算法的时间复杂度是⼀个函数式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，实在是太小了，可以忽略不计，上面写的可以测试运行时间的代码里面，10000次可能运行时间都为0，所以声明的时候可以忽略不记

---

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

⼤O的渐进表⽰法

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

💡 推导⼤O阶规则

1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时， 低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。

2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数 对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。

3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。

通过以上⽅法，可以得到 Func1 的时间复杂度为： O(N²)

注意点：

这里的规则时间复杂度和空间复杂度都能用

时间复杂度计算⽰例

示例1

// 计算Func2的时间复杂度？
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}

示例2

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%d\n", count);
}

示例3

// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}

示例4

// 计算strchr的时间复杂度？
const char * strchr ( const char
* str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}

T（N)取决于要查找的位置

💡 总结 通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。

最坏情况：任意输⼊规模的最⼤运⾏次数(上界)

平均情况：任意输⼊规模的期望运⾏次数

最好情况：任意输⼊规模的最⼩运⾏次数(下界)

⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况

示例5

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

外层循环控制的是我们一次循环要交换多少次，这里的时间复杂度是内层循环交换次数的累加

因此：BubbleSort的时间复杂度取最 差情况为： O(N² )

有个地方要注意区分：

前面的里面有道题也是双层for循环

实际上本质也是外层控制次数，不过这里外层是m,不是具体的常数，不可以忽略掉，所以时间复杂度是M*N

示例6

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}

书籍中 log2 n 、 log n 、 lg n 的表⽰ 当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不 写，即可以表⽰为 log n 不同书籍的表⽰⽅式不同，以上写法差别不⼤，我们建议使⽤ log n,也是因为对数的底数打不出来

示例7

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}

这里不可以理解为单次递归的时间复杂度都是O(1),也要具体情况具体分析，如果说里面嵌套for循环之类的，就可能不是O(1)

这里仅仅是举例一些常见的例子，因为是初阶数据结构，就不展开来讲太多。

空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。

空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复 杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。

注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好 了，因 此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定

空间复杂度计算示例

示例1

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

函数栈帧在编译期间已经确定好了， 只需要关注函数在运⾏时额外申请的 空间。 BubbleSort额外申请的空间有 exchange等有限个局部变量，使⽤了 常数个额外空间 因此空间复杂度为 O(1)

示例2

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}

Fac递归调⽤了N次，额外开辟了N个函数栈帧， 每个栈帧使⽤了常数个空间 因此空间复杂度为： O(N)

注意点：
涉及到动态内存管理也会涉及到空间复杂度的计算，例子如下：

int func()
{
    int arr[n]=(int*)malloc(sizeof(int)*n);
}

这段代码的空间复杂度为O(n)

常见复杂度对比

上图仅需要做个简单的了解即可

相关的小练习

大O表示法

1.下列有关大O表示法的说法错误的是

A.大O表示法只是对程序执行时间的一个估算

B.大O表示法只保留最高阶项

C.大O表示法会保留一个系数来更准确的表示复杂度

D.大O表示法一般表示的是算法最差的运行时间

答案：C

解析：大O是一个渐进表示法，不会去表示精确的次数，cpu的运算速度很快，估计精确的没有意义。

时间复杂度

2.分析以下程序的时间复杂度

for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
    a[i][j]=i*j;

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

答案：B

解析：

程序有两次循环，每个循环都有n次操作，所以时间复杂度为n^2

3.分析以下函数的时间复杂度

void fun(int n) {
  int i=l;
  while(i<=n)
    i=i*2;
}

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

5.下面算法的时间复杂度是（ ）

 int f ( unsigned int n ) {
    if (n == 0 || n==1) 
      return 1;
    else 
      return n * f(n-1);
  }

A.O(n)

B.O(n^2)

C.O(nlogn)

D.O(logn)

答案：A

解析：

此函数会被递归调用n - 1次，每次操作都是一次，所以时间复杂度为n

空间复杂度

2.分析以下函数的空间复杂度（ ）

int** fun(int n) {
    int ** s = (int **)malloc(n * sizeof(int *));
    while(n--)
      s[n] = (int *)malloc(n * sizeof(int));
    return s;
  }

A.O(n)

B.O(n^2)

C.O( 1 )

D.O(nlogn)

答案：B

解析：

此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3,…n列，所以是n(n + 1)/2个元素空间，空间复杂度为n^2

复杂度算法题

旋转数组

给定一个整数数组 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]

示例 2:

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

思路1

时间复杂度 O(n² )

循环K次将数组所有元素向后移动⼀位（代码不通过）

void rotate(int* nums, int numsSize, int k) {
while(k--)
{
int end = nums[numsSize-1];
for(int i = numsSize - 1;i > 0 ;i--)
{
nums[i] = nums[i-1];
}
nums[0] = end;
}
}

思路2：

空间复杂度 O(n)

申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中

void rotate(int* nums, int numsSize, int k)
{
int newArr[numsSize];
for (int i = 0; i < numsSize; ++i)
{
newArr[(i + k) % numsSize] = nums[i];
}
for (int i = 0; i < numsSize; ++i)
{
nums[i] = newArr[i];
}
}

以空间换时间的方式

先申请新的数组，大小为numsSize,[]下标的处理是关键，这是反转数组的关键

代码如下：

void rotate(int* nums, int numsSize, int k)
{
int newArr[numsSize];
for (int i = 0; i < numsSize; ++i)
{
newArr[(i + k) % numsSize] = nums[i];
}
for (int i = 0; i < numsSize; ++i)
{
nums[i] = newArr[i];
}
}

思路3：空间复杂度 O(1)（非常妙的思路）

void reverse(int* nums,int begin,int end)//逆置数组元素
{
while(begin<end)//先判断再执行，=可以不加
{
    //交换数组元素
int tmp = nums[begin];
nums[begin] = nums[end];
nums[end] = tmp;
    //元素移动
begin++;
end--;
}
}
void rotate(int* nums, int numsSize, int k)
{
    //保证k的值不会超过numsSize
k = k%numsSize;
    //前n-k个数据逆置
reverse(nums,0,numsSize-k-1);
    //后k个数据逆置
reverse(nums,numsSize-k,numsSize-1);
    //整体数据逆置
reverse(nums,0,numsSize-1);
}

思维导图