文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

数据结构与算法—时间复杂度和空间复杂度

2023-10-24 06:01

关注

目录

1. 什么是数据结构?

2.什么是算法?

3、算法的复杂度

4、时间复杂度

(1) 时间复杂度的概念:

 (2) 大O的渐进表示法: 

六个例题:

(3) 时间复杂度对比: 

两个例题: 

OJ题分析时间复杂度

5、空间复杂度

(1)常见复杂度对比

 (2)OJ题分析空间复杂度

小结


1. 什么是数据结构?

数据结构 (Data Structure)  是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。
通俗讲就是在内存中管理数据的方式,比如增删查改等操作。

2.什么是算法?

算法 (Algorithm  /ˈælɡərɪðəm/ ) 就是定义良好的计算过程,取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。
比如:我们学过的冒泡排序、二分查找等。

3、算法的复杂度

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

4、时间复杂度

(1) 时间复杂度的概念:

时间复杂度的定义:在计算机科学中, 算法的时间复杂度是一个函数 ,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例, 算法中的基本操作的执行次数,为算法 的时间复杂度
即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。

 

接着来看一个例子:请计算下面代码中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;    }

我们用时间复杂度函数式来表示:F(N)=N*N+2*N+10,稍后进行详细解释

Func1 执行不同次数时的时间复杂度 :

实际中我们计算时间复杂度时, 我们其实并不一定要计算精确的执行次数 ,而只需要大概执行次数,那么这里我们使用 大O的渐进表示法

 (2) 大O的渐进表示法: 

大O符号:是用于描述函数渐进行为的数学符号。 推导大O阶方法:
1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中,只保留最高阶项。 3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后,Func1的时间复杂度为: 通过上面我们会发现大O的渐进表示法 去掉了那些对结果影响不大的项 ,简洁明了的表示出了执行次数。 另外有些算法的时间复杂度存在最好、平均和最坏情况:
  • 最坏情况:任意输入规模的最大运行次数(上界)
  • 平均情况:任意输入规模的期望运行次数
  • 最好情况:任意输入规模的最小运行次数(下界)
例如:在一个长度为N数组中搜索一个数据x 在实际中一般情况关注的是算法的 最坏运行情况 ,所以数组中搜索数据时间复杂度为O(N)

六个例题:

例1:计算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);}

基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)

例2:计算Func4的时间复杂度?

void Func4(int N){    int count = 0;    for (int k = 0; k < 100; ++ k)    {    ++count;    }    printf("%d\n", count);}

基本操作执行了10次,通过推导大O阶方法,时间复杂度:O(1)(不是代表一次,而是代表常数次)

大O阶法规定程序运行常数次的时间复杂度为O(1),尽管运行常数次可能很巨大,但我们不用担心,处理器的速度远超我们想象,一次和一亿次都是以瞬间完成的。

例3:计算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*N+10(M)次,时间复杂度: O(N) 

例4:计算strchr的时间复杂度?

const char * strchr ( const char * str, int character );

strchr函数原型如下:

while(*str){    if(*str == character)        return str;    else        str++;}

所以时间复杂度为str的长度: O(N) 

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

 这个就是冒泡排序,本质上就是等差数列,运用等差数列求和公式即可求出:

 所以时间复杂度为:N*(N-1)/2

例6:计算BinarySearch的时间复杂度?

int BinarySearch(int* a, int n, int x){assert(a);int begin = 0;int end = n - 1;// [begin, end]:begin和end是左闭右闭区间,因此有=号while (begin <= end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid - 1;elsereturn mid;}return -1;}

这也眼熟,就是我们学过的二分查找

我们在下图这个区间进行查找:每次查找一次区间缩小一半,也就是每查找一次除一次 2,

N / 2 / 2 / 2 / …/ 2 = 1 ,直到剩下1个元素或没有元素可查找为止。

假设找了x次,也就是除了x个2,由 2*x=N 得出:x=log2(N) (以2为底N的对数)

(3) 时间复杂度对比: 

暴力查找与二分查找的时间复杂度对比,我们能看出二分查找的效率之高:

 

冒泡排序与qsort(快速排序)—时间复杂度对比:

两个例题: 

 例1:计算BubbleSort的空间复杂度?

long long Fac(size_t N){if (0 == N)return 1;return Fac(N - 1) * N;}

这是一个递归函数,运行过程如下:

运行N+1次去掉常数,则时间复杂度为:O(N) 

 例2:计算阶乘递归Fac的时间复杂度

运行过程如下,时间复杂度为:O(N^2)

例3:计算斐波那契递归Fib的时间复杂度? 

long long Fib(size_t N){if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);}

这个递归函数运行的过程如下:

可以看出斐波那契数列本质就是一个等比数列,虽然在最后Fib(2)无法往下分,但计算时间复杂度可以忽略这一块,它对复杂度的影响很小。

接下来我们可以使用等比数列求和公式:

用求和公式计算有点麻烦,这里推荐使用高中所学的错位相减法进行计算:

计算过程如下: 

OJ题分析时间复杂度

接下来通过一道题来分析时间复杂度: 

第一种方法:排序,再一次查找,如果下一个数不是上一个数加一,则上一个数加一就是消失的数字。这种方法的时间复杂度为 O(N*logN)

第二种方法:异或运算,一个数字与0进行异或运算两次还是0,如果把数组中的元素与正常0到n的元素都与一个值为零的变量进行异或,最终剩下的就是缺失的数字,也就是 x 的值。

代码如下:

int missingNumber(int* nums, int numsSize) {    int x = 0;    for (int i = 0; i < numsSize; i++)        x ^= nums[i];    for (int i = 0; i < numsSize + 1; i++)        x ^= i;    return x;}

设置变量x=0,遍历数组中每个元素与 x 异或运算,然后再遍历0到n所有数字与 x 进行异或运算,最终得到缺失数字 x 。

第三种方法:利用等差数列公式求 0 到 n 的和,再减去数组中已有元素,得到消失的元素。

代码如下:

int missingNumber(int* nums, int numsSize) {    int x = (1 + numsSize) * numsSize / 2;    for (int i = 0; i < numsSize; i++)        x -= nums[i];    return x;}

5、空间复杂度

空间复杂度也是一个数学表达式,是对一个算法在运行过程中 临时占用存储空间大小的量度 空间复杂度不是程序占用了多少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;}}
该程序使用了常数个额外空间,所以空间复杂度为 O(1)

例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;}
动态开辟了N个空间,空间复杂度为 O(N)

例3:计算阶乘递归Fac的空间复杂度?

long long Fac(size_t N){if (N == 0)return 1;return Fac(N - 1) * N;}
递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)。 空间的销毁是归还使用权,内存空间属于操作系统的进程。 具体过程如下:(运行过程按照图中标记)

(1)常见复杂度对比

 (2)OJ题分析空间复杂度

 我们有三种方法:

假设数组为

  1. 前n-k个逆置:这种情况下,我们需要将数组的前n-k个元素逆置。可以通过交换数组头部和尾部的元素,然后逐步向中间逼近完成逆置。时间复杂度为O((n-k)/2),空间复杂度为O(1),因为只需要有限的额外空间来保存中间变量。
  2. 后k个逆置:对于后k个逆置,同样可以采用头尾交换的方式逐步逼近完成逆置。时间复杂度为O(k/2)。
  3. 整体逆置:整体逆置即将整个数组逆置,可以通过两个指针分别从数组两端向中间遍历,依次交换对应位置的元素实现。时间复杂度为O(n/2)。
  4. 总的时间复杂度为这三种情况的时间复杂度之和,即O((n-k)/2)+O(k/2)+O(n/2)=O(n)

代码如下: 

void reserve(int* a,int left,int right){    while(leftnumsSize)        k%=numsSize;    reserve(nums,numsSize-k,numsSize-1);    reserve(nums,0,numsSize-k-1);    reserve(nums,0,numsSize-1);}

通过创建新的数组接收复制的元素实现旋转效果。

代码如下: 

void rotate_1(int* nums, int numsSize, int k){if (k > numsSize)k %= numsSize;int* tmp = (int*)malloc(sizeof(int) * numsSize);memcpy(tmp + k, nums, sizeof(int) * (numsSize - k));memcpy(tmp, nums + numsSize - k, sizeof(int) * (k));memcpy(nums, tmp, sizeof(int) * (numsSize));free(tmp);tmp = NULL;//可以不置空,出函数局部变量tmp就被销毁了}

小结

我们通过概念讲解与实例结合,将复杂度进行了讲解,希望这篇文章对你有帮助!!!

来源地址:https://blog.csdn.net/m0_73800602/article/details/133673204

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯