当前位置: 首页 > news >正文

数据结构第一章复杂度的认识

一.复杂度的概念

1.复杂度的分类

在数据结构这门课程中,复杂度分为时间复杂度和空间复杂度。两者对应着不同的计算方法,下面我将一一讲解。

2.复杂度的理解

时间复杂度:该复杂度用来衡量算法的时间效率,并不是代码的具体运行时间。

空间复杂度:该复杂度用来衡量算法的空间效率,并不是计算代码占用多少字节的空间。

目前比较看重时间复杂度,因为目前市面上对节省空间的需求越来越少,因此时间效率便成为了看重的目标。

二.时间复杂度

1.计算方法

时间复杂度的计算方法是计算该算法的大概执行次数(估算)。

2.引例

请计算下列代码的时间复杂度

void Func1 (int N)
{int count=0;for(int i=0 ; i<N ; i++)//外循环执行N次{for(int j=0; j<N; j++)//内循环执行N次{count++;}}for(int k=0;k<2*N;k++)//此循环执行2*N次{count++;}int M=0;while(M--)//这个while循环执行M次,也就是10次。{count++;}printf("%d",count);
}

上述代码的具体执行次数为N*N+2*N+10,并且随着N的增大该代码执行的次数也随之增大。且表达式中的N^2对执行次数影响最大。

因为时间复杂度的计算是估算,应该选择表达式中影响最大的那一项,所以该代码的时间复杂度为O(N^{}^2)。(括号内是N平方的意思)

上面时间复杂度的表达手法被叫做大O的渐进表示法,主要是由一个大写的字母O和估算出来的时间复杂度构成,下面来说一下这个大O的渐进表示法。

3.大O的渐进表示法

(1)常用数字1取代运行时间复杂度表达式中的所有常数项。

(2)在修改后的运行次数函数中,只保留最高阶的那一项。

(3)如果最高项的系数不为1,应该把它的系数换成1。

这样得出的最终结果便是算法的复杂度。

4.练习

(1)写出函数Func2的时间复杂度

    void Func2 (int N){int count =0;for(int k=0; k<2*N; k++)//循环了2*N次count++;int M=10;while(M--)//while循环了M次,也就是10次。count++;printf("%d",count);}

上述代码的具体执行次数为2*N+10,留住最高阶项,同时把最高项的系数换为1。得到了该算法的时间复杂度为O(N)。

(2)写出函数Func3的时间复杂度

void Func3 (int N)
{int count=0;for(int k=0; k<M;k++)//该循环了M次count++;for(int j=0; j<N; j++)//该循环了N次count++:printf("%d",count);
}

上述代码的具体执行次数为M+N,所以上述代码的时间复杂度为O(M+N)。

        注意:时间复杂度最后得出的结果不一定只有一个未知量,如上算法的时间复杂度便有两个未知量:M和N。

(3)写出函数Func4的时间复杂度

void Func4 (int N)
{int count =0;for(int k=0;k<100;k++)//该循环了100次count++;printf("%d",count);
}

上述代码的具体执行次数为100。根据大0渐进法的定义第一条:用常数1替换掉所有的时间表达式中的常数项。所以该算法的时间复杂度为O(1)。

        注意:如果时间复杂度为O(1),则说明该算法随着输入的N变大,时间效率是固定不变的。这也暗示O(1)是时间效率最高的代码!

(4)写出函数strchr的时间复杂度

const char* strchr (const char* str, char character)
{while(*str !='\0')//如果*str为'\0',也就是循环到*str字符串结尾的时候,终止循环。{if(*str == character)//如果此时的*str和目标数据character相同return str;//就返回这个*str的地址str++;//如果不相等,就继续循环,一直到循环终止为止}return NULL;//如果遍历了整个字符串,依然没有找到,就返回NULL。
}

上述代码的作用是:找到一个字符串中需要的字符并返回,如若没找到则返回NULL。

该代码的具体执行次数应该分情况讨论,(先假设字符串的长度为N)

最好的情况就是第1次就找到了,具体的执行次数就是1;

最坏的情况就是遍历了整个字符串都没有找到,具体的执行次数就是N。

不好不坏的情况(平均情况)就是遍历字符串到一半的时候找到了,具体的执行次数为N/2。

如上,便是所有情况下,算法的具体执行次数。那么我们应该选择哪一个呢??应该选择第一种:报喜不报忧,还是平均的情况呢?其实都不是。我们在计算时间复杂度时,如果遇到此类型需要分类讨论的题目时,我们应该使用最坏的情况。(只要最坏的情况能让别人接受,那么该算法就算通关了!!)

(5)写出函数BinarySearch的时间复杂度

int BinarySearch (int *a, int n,int x)
{assert(a);//判断a地址是否正确,正确则程序继续,错误则打印错误。int begin=0;int end=n;while(begin<end)//当begin大于等于end时循环终止{int mid= begin +((end-begin)>>1);//>>为右移操作符,a>>1的具体效果是a除以2.if(a[mid]<x)begin= mid+1;else if(a[mid]>x)end =mid;else return mid;}return -1;
}

上述代码是一个二分查找的C语言代码,主要作用是在一个数组中找到一个数。

假设数组长度为N。

最好的情况是第一次就找到了,该情况的具体执行次数是1。

平均情况是遍历数组到一半的时候找到了目标数,此时该情况的具体执行次数为N/2。

最坏的情况就是一直在折半查找,折半到最后一步才找到(或者折半到最后一次也没有找到),此时,该情况的具体执行次数为_{}(以2为底N的对数)。解析:每次折半都会消失数组中一半的数据,等到消失到只有一个数据时,就结束了。假设最坏情况下的执行次数为x,那么2^x=N,所以最坏情况下的具体执行次数x为(以2为底N的对数)。

最后得出该函数的时间复杂度为O(logN)。一般情况下会省略底数,原因也很简单,计算机键盘不好输出对数函数的形式,所以省略底数。

(6)写出Factorical函数的时间复杂度

longlong Factorical (int N)
{return N<2?N:Factorical(N-1)*N
}

上述代码运行递归的手法,自己调用自己,完成了阶乘的计算。具体的执行次数为N次,所以该算法的时间复杂度为O(1)。

5.算法效率排行

在写代码的时候,不同的代码有着不同的时间复杂度,因为时间复杂度是用来计算代码运行的时间效率的,所以也可以根据时间复杂度来得知该代码的效率。下面给出不同时间复杂度的效率排行。

O(1)>O(logN)>O(N)>O(N*logN)>O(N^2)>O(2*N)>O(N!)

 三.空间复杂度

1.概念

空间复杂度:对一个算法在运行过程中临时占用存储空间大小的量度,并不是计算具体占用多少字节的空间,而是计算变量的个数。(同样满足大O渐进表示法)

2.练习

(1)写出BubbleSort函数的空间复杂度

void BubbleSort (int *a,int n)
{assert(a);//判断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;}
}

上述代码一共创建了5个变量,所以该函数的空间复杂度为O(1)

需要注意的是,循环创建的变量一直在重复利用他同一块空间,不用重复计算,也就是说:时间是累积的,空间是不累积的。

(2)写出Fibnacci函数的空间复杂度

longlong *Fibnacci (size_t n)//1
{if(n==0)return NULL;longlong *fibarray=(longlong *)malloc ((n+1)*size of(longlong));//fibarray为一个,后面又申请了N+1个fibarray[0]=0;//1fibarray[1]=1;//1for(int i=2; i<=n; i++)//1{fibarray [i]=fibbarray[i-1] +fibarray[i-2];}return fibarray;
}

上述代码一共开辟了N+6个变量,根据大O的渐进表示法,该函数的空间复杂度为O(N)。

(3)写出Factorical函数的空间复杂度

longlong Factorical (size_t N)
{return N<2?N:Factorical(N-1)*N;
}

        上述代码是一个递归函数 ,自己递归调用自己 ,每次递归调用都会建立一个栈帧,每次栈帧的创建都会使用一个常数空间。上面的算法,每次建立栈帧会创建一个变量,所以具体创建的变量的个数就等于创建的栈桢数(递归调用函数的次数),所以上述代码的空间复杂度为O(N)。

四.OJ练习题

1.题目一

        题目描述:有一个数组nums包括从0到n的所有整数,但是里面缺一个数字,请以时间复杂度为O(1)的代码找出这个数。

        示例:输入:[9,6,4,2,3,5,7,0,1]

                   输出:8

思路一:因为给出的数组是乱序,所以先给数组进行排序。排好顺序之后,遍历数组,找出缺少的那个数字。但是这个思路的时间复杂度不满足题意,舍去!!

下面是思路一的代码实现:

#include <stdio.h>// 写出swap函数,使用传址调用
void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}int main()
{int nums[9];for (int i = 0; i < 9; i++){scanf("%d", &nums[i]);}// 冒泡排序算法for (int j = 0; j < 8; j++) {for (int k = 0; k < 8 - j; k++) {if (nums[k] > nums[k + 1]) {swap(&nums[k], &nums[k + 1]);}}}// 查找并输出缺失的数字int flag = 0;for (int k = 0; k <= 9; k++) {  // 检查0-9的数字flag = 0;for (int i = 0; i < 9; i++){if (nums[i] == k) {flag = 1;break;  // 找到后可以提前退出内层循环}}if (flag == 0) {printf("%d ", k);  // 输出缺失的数字}}return 0;
}

思路二:将给出的数组全部加起来记作结果一,然后把数字0-N全部加起来记作为结果二。然后用结果二减去结果一就是缺失的那个数字。

思路三:将给出的数组和0-N的所有数据按位异或,最后得到的答案就是缺失的那个数字。

下面是思路三的代码实践:

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

2.题目二

        题目描述:给定一个数组,将数组中的元素向右移动k个位置,其中k>=0。(空间复杂度控制在O(1)。)

        示例:输入:nums=[1,2,3,4,5,6,7]  k=3

                   输出:           [5,6,7,1,2,3,4]

                   解释:向右旋转第一步:[7,1,2,3,4,5,6]

                              向右旋转第二步:[6,7,1,2,3,4,5]

                              向右旋转第三步:[5,6,7,1,2,3,4]

思路一:旋转k次,每次把最后一个元素放到第一位,此算法的缺点是当数组中的数据过于庞大,时间复杂度就会变大,所以次算法不推荐。

下面是思路一的代码实践:

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

思路二:创建一个新的数组,让旧数组后k个值赋值到新数组的前k位置上,让旧数组前k个元素赋值到新数组的后k个位置上。最后把新数组整体赋值给旧数组上。

思路三:让后k个元素逆置一次,然后让前n-k个元素逆置一次,最终让整个数组逆置一次,便能神奇地得到结果数组。

以下是思路三的代码实践:

void Reverse (int *nums,int left,int right)//写一个逆置函数
{while(left<right){int tmp=nums[left];nums[left]=nums[right];nums[right]=tmp;left++;right--;}
}
void ROtate(int *nums,int numsSize,int k)
{if(k>=numsSize)//如果k大于数组的大小,对k进行处理,而后程序继续k%=numsSize;Reverse(nums,numsSize-k,numsSize-1);//分三次逆置,得到目标数组Reverse(nums,0,numsSize-k-1);Reverse(nums,0,numsSize-1);
}

http://www.xdnf.cn/news/1102087.html

相关文章:

  • 【java17】使用 Word 模板导出带替换符、动态表格和二维码的文档
  • iOS 数组如何设计线程安全
  • 提示工程:突破Transformer极限的计算科学
  • 工具分享--IP与域名提取工具
  • Spring 声明式事务:从原理到实现的完整解析
  • 小架构step系列11:单元测试引入
  • 分享|2025年机器学习工程师职业技术证书报考指南
  • 如何使用 Python 删除 Excel 中的行、列和单元格 – 详解
  • 《探索电脑麦克风声音采集多窗口实时可视化技术》
  • xFile:高性能虚拟分布式加密存储系统——Go
  • 上位机知识篇---Git符号链接
  • python的类型注解讲解
  • 云、实时、时序数据库混合应用:医疗数据管理的革新与展望(中)
  • 电力自动化的通信中枢,为何工业交换机越来越重要?
  • NLP_知识图谱_大模型——个人学习记录
  • CentOS 安装 JDK+ NGINX+ Tomcat + Redis + MySQL搭建项目环境
  • LVS-NAT模式配置
  • Java语言基础
  • Windos服务器升级MySQL版本
  • 从Excel到PDF一步到位的台签打印解决方案
  • 5G标准学习笔记14 - CSI--RS概述
  • 《磁力下载工具实测:资源搜索+高速下载一站式解决方案》
  • P1204 [USACO1.2] 挤牛奶Milking Cows
  • 【Linux】GDB/CGDB 调试器学习笔记
  • 实现在线预览pdf功能,后台下载PDF
  • 【web应用】若依框架中,使用Echarts导出报表为PDF文件
  • SSL与HTTP概述
  • 【网络编程】KCP——可靠的 UDP 传输协议——的知识汇总
  • 华为VS格行VS中兴VS波导随身WIFI6怎么选?流量卡OR随身WIFI,长期使用到底谁更香?
  • leetcode 3169. 无需开会的工作日 中等