数据结构(C语言实现)|数据结构和算法复杂度简述


文章目录

  • 1.数据结构前言
    • 1.1 什么是数据结构?
    • 1.2 什么是算法?
    • 1.3 如何学好数据结构和算法
    • 1.4 数据结构和算法书籍及资料推荐
  • 2.算法的时间复杂度和空间复杂度
    • 2.1 算法效率
      • 2.1.1 如何衡量一个算法的好坏
      • 2.1.2 算法的复杂度
      • 2.1.3 复杂度在校招中的考察
    • 2.2 时间复杂度
      • 2.2.1 时间复杂度的概念
      • 2.2.2 大O的渐进表示法
      • 2.2.3 常见时间复杂度计算举例
    • 2.3 空间复杂度
    • 2.4 常见复杂度对比
    • 2.5 复杂度的oj练习

1.数据结构前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。
1.2 什么是算法? 算法(Algorithm)就是定义良好的计算过程,他取一个或一组值作为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。
1.3 如何学好数据结构和算法 1. 死磕代码
数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

2. 注意画图和思考
数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

1.4 数据结构和算法书籍及资料推荐
  1. 剑指offerOJ
    数据结构(C语言实现)|数据结构和算法复杂度简述
    文章图片
  2. LeetCode OJ
2.算法的时间复杂度和空间复杂度 2.1 算法效率 2.1.1 如何衡量一个算法的好坏
比如对于以下斐波那契数列:
long long Fib(int N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }

斐波那契数列的递归实现方式非常简洁,但简洁一定好吗?那该如何衡量其好与坏?
2.1.2 算法的复杂度
算法在编写成可执行程序后,运行时需消耗时间资源和空间(内存)资源。因此 衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的, 即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。 在计算机发展的早期,计算机的存储容量很小。所以空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
2.1.3 复杂度在校招中的考察
数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

2.2 时间复杂度 2.2.1 时间复杂度的概念
时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间,一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是很麻烦,所以才有了时间复杂度这个分析方式。一个算法
// 请计算一下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; } printf("%d\n", count); }

【数据结构(C语言实现)|数据结构和算法复杂度简述】数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只要大概执行次数,那么这里我们使用大O的渐进表示法。
2.2.2 大O的渐进表示法
大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大O阶方法:
  1. 用常数1取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项项。
  3. 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后,Func1的时间复杂度为:
O(N^2)

  • N = 10 F(N) = 100
  • N = 100 F(N) = 10000
  • N = 1000 F(N) = 1000000
    通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。
    另外有些算法的时间复杂度存在最好、平均和最坏情况:
    最坏情况:任意输入规模的最大运行次数(上界)
    平均情况:任意输入规模的期望运行次数
    最好情况:任意输入规模的最小运行次数(下界)
    例如:在一个长度为N数组中搜索一个数据x
    最好情况:1次找到
    最坏情况:N次找到
    平均情况:N/2次找到
    在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)
2.2.3 常见时间复杂度计算举例
实例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); }

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

实例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); }

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

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

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

实例4:
// 计算strchr的时间复杂度? const char * strchr ( const char * str, int character ) { while(*str) { if(*str == character) return str; else ++str; } return NULL; }

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

实例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; } }

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

最坏情况就是等差数列求和,最好情况就是序列本身就有序,虽然没有发生交换,但仍要进行N-1次比较
实例6:
// 计算BinarySearch的时间复杂度? int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n; while (begin < end) { int mid = begin + ((end-begin)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid; else return mid; } return -1; }

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

这里简单说一下二分查找的边界处理:
  1. 如果你习惯于前闭后开,那么后续处理也应写成前闭后开。
    数据结构(C语言实现)|数据结构和算法复杂度简述
    文章图片

    代码如实例6所示。
  2. 如果你习惯于全部闭区间,那么后续处理也应写成全闭区间。
数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

代码如下:
int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n-1; while (begin <= end) { int mid = begin + ((end-begin)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid-1; else return mid; } return -1; }

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

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

实例8:
// 计算斐波那契递归Fib的时间复杂度? long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

2.3 空间复杂度
空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少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; } }

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

实例2:
// 计算Fibonacci的空间复杂度? // 返回斐波那契数列的前n项 long long* Fibonacci(size_t n) { if(n==0) return NULL; long long * fibArray = (long long *)malloc((n+1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n ; ++i) { fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; } return fibArray; }

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

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

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

实例答案及分析:
  1. 实例1使用了常数个额外空间,所以空间复杂度为 O(1)
  2. 实例2动态开辟了N个空间,空间复杂度为 O(N)
  3. 实例3递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)
附加题:
// 计算斐波那契递归Fib的空间复杂度? long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

我们发现栈空间是有限的,如果递归次数过多很容易引发栈溢出问题,为了减轻这个影响,栈空间回收以后可以重复利用的
请看以下例子:
数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

2.4 常见复杂度对比
一般算法常见的复杂度如下:
数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

2.5 复杂度的oj练习
  1. 消失的数字oj练习
数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

咱们用异或的方式敲一下代码:
int missingNumber(int* nums, int numsSize){ int x = 0; for(int i=0; i

  1. 旋转数组oj链接
数据结构(C语言实现)|数据结构和算法复杂度简述
文章图片

我们用第三种数组翻转的方式敲一下代码:
void reverse(int *a, int left, int right) { while(left < right) { int tmp = a[left}; a[left] = a[right]; a[right] = tmp; ++left; --right; } }void rotate(int *nums, int numsSize, int k) { k %= numsSize; reverse(nums, 0, numsSize-k-1); reverse(nums, numsSize-k, numsSize-1); reverse(nums, 0, numsSize-1); }

    推荐阅读