C语言数据结构时间复杂度及空间复杂度简要分析
一、时间复杂度和空间复杂度是什么?
1.1算法效率定义
算法效率分为两种,一种是时间效率——时间复杂度,另一种是空间效率——空间复杂度
1.2时间复杂度概念
时间复杂度,简言之就是你写一个代码,它解决一个问题上需要走多少步骤,需要花费多长时间。打个简单的比方:现在给10个数,要求找到7在哪里1,2,3,4,5,6,7,8,9,10。我们要求写一个代码,同学狗蛋写了一个暴力查找,从第一个数依次往后遍历,他的算法要找7次,同学狗剩写了一个二分法查找,只要找2次,这就是时间复杂度的比较
算法中的基本操作的执行次数,为算法的时间复杂度
1.3空间复杂度概念
空间复杂度,是对一个算法在运行过程中临时占用存储空间大小的量度。举个栗子:我们现在要求写一个代码,狗蛋啪啪啪敲了一大堆变量,程序运行了,狗剩就用了很少的变量,程序也运行了。但是他们两个在代码运行中变量多少不同,占用的内存多少是不一样的。空间复杂度,它计算的是变量的个数。
二、如何计算常见算法的时间复杂度和空间复杂度
我们在计算时间/空间复杂度时用的都是大O渐进表示法(是一种估算法)
2.1时间复杂度计算
我们以一个简单的函数举例
代码如下:
void func1(int n) { int i = 0; int j = 0; int k = 0; int count = 0; for (i = 0;i < n;i++) { for (j = 0;j < n;j++) { count++; } } for (k = 0;k < 3 * n - 1;k++) { count++; } }
试问:该函数如果被调用,要运行多少次?
我们清楚的看出i进去有n次,共有n个i,第一个for结束要运行n^ 2次,第二个for要执行3n-1次,共执行n^ 2+3n-1次
那么我们这里的时间复杂度是否就是n^2+3n-1呢?答案是否的
我们前面说过,时间复杂度和空间复杂度用的都是大O渐进表示法,是一种估算法
我们取的值,是取对表达式中影响最大的那个
我们以n^ 2+3 * n-1这个式子进行举例:设f(n)=n^2+3n-1
n=1,f(n)=1+3-1=3
n=10,f(n)=100+30-1=129
n=100,f(n)=10000+300-1=10299
n=1000,f(n)=1002999
…
很容易发现,对f(n)影响最大的是n^ 2,设g(n)=n^2
n=1,g(n)=1
n=10,g(n)=100
n=100,g(n)=10000
n=1000,g(n)=1000000
…
当n越大,g(n)就越接近f(n)
那么这里的时间复杂度大O渐进表达法写法是这样的:O(n^2)
2.2空间复杂度计算
在学习空间复杂度的求解之前,我们要知道,空间复杂度也是用大O渐进表达法进行求解,我们计算的不是所占空间大小,而是变量的个数。先来看一段代码:
代码如下(示例):
#include<stdio.h> 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; } }
在上面这个代码中,我们创建了三个变量分别是size_t end
、int exchange
、size_t i
,尽管我们这个函数会经历很多的循环,但这三个变量是反复使用的,也就是说他们所占的空间是被反复使用的,空间的多少是没有变的,这里区别时间复杂度——时间是累计的,空间是不累计的(对于时间复杂度,每次循环都会被计算;对于空间复杂度,空间是可以被反复使用的)。
我们上面说过,空间复杂度计算也是用的大O渐进表示法,对于常数,我们统一用O(1)表示(大O渐进表示法详情见时间和空间复杂度篇1)
ps1:assert通常用于诊断程序中潜在的BUG,通过使用assert(condition), 当condition为false时,程序提前结束运行,利于程序BUG的定位。
ps2:size_t是一种类型,把它看作long unsigned int
我们再来看一段代码:
代码如下(示例):
//计算bubblesort的空间复杂度 #include<stdio.h> long long Factorial(size_t n) { return N < 2 ? N : Factorial(n - 1)*n; }
这段代码是一个很简单的递归实现阶乘运算,那么它的空间复杂度是多少呢?我们先假设传过去的n=10。
10传过来我们会进行10次递归,每次递归是创建一个函数栈帧(也就是一个空间),共创建10次,每一次的空间复杂度都是O(1)。把10换成n,也就是进行n次递归,每次递归会创建1个函数栈帧,空间复杂度是O(n)。
ps:可能会有小伙伴问,那函数栈帧递归往回走的时候不是销毁了吗?注意:这里的空间复杂度是计算的“最坏、最多的情况”,况且不管是什么函数,在使用过后其栈帧都会销毁,空间复杂度算的是它用的空间最多的时候。
2.3快速推倒大O渐进表达法
1.常数1代替所有加法运算中的常数
2.只保留最高阶(高数极限思想)
3.若最高阶存在且不为常数,则去除最高阶的系数,比如3*n^ 9,去掉系数变为n^9
我们再来看两个代码训练一下
代码1如下:
void func2(int n) { int i = 0; int k = 0; int count = 0; for (i = 0;i < 3n;i++) { count++; } for (k = 0;k < 6;k++) { count++; } }
这里f(n)=3n+6,它的大O渐进表达法就是O(n)
代码2如下:
void func3(int n) { int i = 0; int count = 0; for (i = 0;i < 1000;i++) { count++; } }
这里一眼就看出是运行1000次,用什么来表示呢?前面说过:常数1代替所有加法运算中的常数,所以这里不管常数有多大,只要你只有一个常数都用O(1)表示
一些注意事项:
O(1)这个时间复杂度的估值是不随n的改变而改变的,以大白话说,不管你输入的n是多少,我这个算法的效率是不变的
O(n)这个时间复杂度是随n改变的
打个通俗的比方:设一个函数O(x)=1,那你x随意多少,函数值都是1
设一个函数O(X)=x,那这里函数值就随x变换而变换了
三、一些特殊的情况
有些算法的时间复杂度是存在最好、平均、最坏情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)
不多说,举例说明:
代码如下:
const char*strchr(char*str, char c) { while (*str != '\0') { if (*str == c) { return str; } ++str; } return NULL; }
上面的代码是一个简单的查找字符的函数,比如我们现在给一串字符共n个字符“aaaaba…aaac”(省略号省略a)
这里查找a一下子就找到了,查找b要点功夫,查找c就更慢了,如果查找d,不好意思,查无此d。
那么这里就出现了最好情况:一次找到O(1)
平均情况:O(n/2)
最差情况:O(n)
对于这里最坏情况可能有同学要说为什么是O(n),你看最坏情况没找到不是吗?这里解释是这样的,你找c要n次,找d是找不到也要找n次才能确定找不到。
总结
本文介绍了时间和空间复杂度的定义及大O渐进表达法的算法及一些特殊情况的解释,希望对屏幕前的读者有所帮助,祝您学习愉快!
更多关于数据结构时间复及空间复杂度的资料请关注猪先飞其它相关文章!
原文出处:https://blog.csdn.net/m0_57180439/article/details/120143364
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25