…
文章目录
复杂度是衡量一个算法好坏的标准,可以从 时间
和 空间
两个维度进行比较。可能你之前听说某个算法的时间复杂度是O(N),空间复杂度是O(1),知道这是一个还不错的算法,那么你知道这些复杂度是如何计算出来的吗?本文将会揭开它们神秘的面纱,让你拥有一把衡量算法好坏的度量衡。
先说结论
- 时间复杂度主要是
衡量一个算法的运行快慢
,通常由循环决定- 空间复杂度主要是
衡量一个算法运行所需的额外空间
,通常由开辟的空间大小决定
常见错误理解
- 时间复杂度是就是一段代码实际运行运行所花的时间。这种理解是错误的,因为环境的不同会导致代码运行的快慢,比如将一个大型程序放在你电脑上运行,和放在神威·太湖之光上运行所花的时间是肯定不同的,为了统一评判,我们将
算法中基本操作的执行次数
,称为算法的时间复杂度- 空间复杂度和代码长度有关,代码码越长越复杂。错误,假如我们只创建了常数个变量,纵使代码写的再长,这个算法的空间复杂度也是O(1),在
程序中创建的变量个数(在内存中申请的空间大小)
,称为空间复杂度,创建的变量数越多,算法所占空间就越复杂
当然这只是最基本的知识,关于时间&空间复杂度的更多知识可以往下看
在计算机科学中,算法的时间复杂度是一个函数,它定量地描述了该算法的运行时间
同大多数读者一样,我也不喜欢冗长复杂的官方解释,通俗来说,算法中基本操作的执行次数(循环部分)
,就是代表了该算法的时间复杂度,比如下面这段代码
//请问这段代码的时间复杂度是多少?
int main()
{
int N = 0;
scanf("%d", &N);
int count = 0;
int i = 0;
for (i = 0; i < N; i++)
{
count++;
}
return 0;
}
直接看循环部分,可以看到这个算法会循环N次,N是可变的,因此这个算法的时间复杂度就是N,简单吧,当然这只是一个最简单的例子,真实的程序循环比这复杂得多,此时就需要一个工具:大O渐进表示法
,来帮助我们计算出算法的时间复杂度
大O
符号:是用来描述函数渐进行为的数学符号,这个符号有点像数学中取极限
大O渐进表示法
的推导步骤:
2N ^ 2 + 2N + 100
,需要去掉常数项1002N ^ 2 + 2N
,显而易见 2N ^ 2
要大于 2N
,2N ^ 2
就是这里的最高阶项2N ^ 2
,常数项 2
对整体时间复杂度影响是不大的,应该去除以上就是通过 大O渐进表示法
求时间复杂度的步骤,当然示例中的时间复杂度最终为O(N ^ 2)
大O渐进表示法
这样表示,是否合理呢?
答:很合理,尤其是放在计算机上使用
首先假设存在这么一个时间复杂度(不用
大O渐进表示法
版): F(N) = N^2 + 2 * N + 10
经过大O渐进表示法
处理后,变成 F(N) = O(N^2),让我们来测试一组数据:
N F(N) = N^2+2*N+10 F(N) = O(N^2) 相差率 10 100+20+10 = 130 100 23% 100 10000+200+10 = 10210 10000 2% 10000 100020010 100000000 0.02% 显然,随着数据的不断增大,二者间的差距会越来越小,而经过
大O渐进表示法
计算后的时间复杂度,是更容易计算的,除非追求精确的数据,否则用大O渐进表示法
是很合理的~
大O渐进表示法
的核心作用就是去除那些对结果影响不大的项
时间复杂度这一块有几个比较经典的题目需要掌握一下,学会使用 大O渐进表示法
求出时间复杂度
// 计算Func1的时间复杂度?
void Func1(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);
}
答案:
O(N + M)
因为这里有两次循环,并且N
和M
都是未知数,无法区分出谁是最高阶项,因此两个都取出,都没有带常数项,不做去除操作。综上Func1
的时间复杂度就是O(N + M)
// 计算Func2的时间复杂度?
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
答案:
O(1)
显然,这里需要循环100次,都是常数项,直接遵循推导步骤一,时间复杂度为O(1)
这里只循环了100次,即使循环1k次、1w次,也都是常数项,一样是O(1)
//计算strchr的时间复杂度?
const char* strchr(const char* str, int character);
答案:
O(N)
说明:strchr
是一个字符串寻找函数,作用是在字符串str
中查找目标字符character
有三种情况:
- 最好的情况,只找一次,此时的时间复杂度为
O(1)
- 最坏的情况,没有
目标字符
,需要把整个字符串
找一遍,时间复杂度为O(N)
- 平均的情况,在中间就找到了,时间复杂度是
O(N / 2)
面对这种多分支情况,我们要做预期管理,用最悲观的态度来判断程序,这样做的好处是预期值低,结果出来时不会有很大落差,生活中也可以像这样,做好准备。言归正传,这里选择最坏的情况,即
O(N)
,当然这种情况比较特殊,值得注意一下
//计算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(N ^ 2)
冒泡排序是一个神奇的算法,每次冒泡比较的趟数都不同,可以这样推导
- 第一趟:比较 N - 1 次
- 第二趟:比较 N - 2 次
- 第三趟:比较 N - 3 次
- …………
- 最后一趟: 比较 1 次
总共比较的次数,就是时间复杂度,即 (N - 1) + (N - 2) + …… + 1,显然这是一个首项为 N - 1,尾项为 1 的等差数列,并且共有 N - 1 项,把高中学的知识用起来,N - 1 项和为
(N - 1) * N / 2
,通过大O渐进表示法
进行计算,最终结果为O(N ^ 2)
//计算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;
else
return mid;
}
return -1;
}
答案:
O(logN)
折半查找
,一个站在巨人肩膀上的算法,假如我们想在世界范围内找一个人(假设有70亿人,且数据已排序),通过二分查找
,最多只需要查找33次,就能找出这个人,厉害吧?下面是二分查找
的推导过程
假设需要查找的次数为 k 次,那么可以这样写
- N / 2 -> N / 2 ^ 1
- N / 4 -> N / 2 ^ 2
- N / 8 -> N / 2 ^ 3
- …………
其中,左边的序号就是查找的次数 k ,可得出式子
N = 2 ^ k
,稍微变换下,得到k = logN
,其中第二个式子就是二分查找
的时间复杂度,可能细心的人能发现,我没有写底数2
,不是不写,而是不好写,除非文本编辑器支持插入数学式,否则这个是很难表示的,鉴于这个东西应用的广泛性,有这样一个规定:在底数为2
时,可以不写底数;如果底数为其他数,就需要写出来,其他底数都很少见的。 在有的地方,会把lgN
看作logN
,第一种方法是有歧义的,和以10
为底的对数表示形式一致,这是不太好的,但如果我们看到了,要明白lgN
也是一个以2
为底的对数
二分查找
为何厉害?因为二分查找
在计算时,每次都是对半查找
,即2 ^ k
,是一个指数爆炸级查找,因此很快就能找到目标数,听说过一张纸对折64次就能碰到月球的故事吧?指数爆炸是个很庞大的数据
//计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
答案:
O(2 ^ N)
递归本来就是一个很麻烦的东西,更何况这是计算斐波那契数列
- 递归中的时间复杂度,计算的是每次递归中执行次数的累加
我们可以将递归斐波那契数列水平展开,即
1+2+4+8+16+32+……+2^N
根据大O渐进表示法
,去除影响小的常数项,最终结果为O(2 ^ N)
10.24更正
说O(2 ^ N)
是斐波那契数列的时间复杂度有些不准确,因为将斐波那契数列递归求值展开成一颗二叉树后,会发现这是一颗普通二叉树,部分节点有缺失,O(2 ^ N)
用来描述满二叉树合理些。斐波那契数列的详细时间复杂度为O(1.618 ^ N)
,更详细的是一个无理数的指数级
,想了解的可以看看这篇文章 递归求解斐波那契数列的时间复杂度问题
相信你看完这些经典例题后,能对 大O渐进表示法
有一个新的认识,加油,你会越来越强的!
算法的空间复杂度是指临时占用储存空间大小的量度
简单理解,空间复杂度是算法中变量的个数(申请的空间大小)。因为变量在使用前,要先声明,而声明会在内存中开辟空间,无论是在堆上还是栈上,都会造成内存损耗,损耗越大,空间复杂度就越高 ,先看代码:
//空间复杂度
int main()
{
int a = 1;
int b = 2;
int c = 3;
return 0;
}
看变量个数,有a、b、c三个变量,属于常数次,所以这个程序的空间复杂度是 O(1)
,空间复杂度也遵循大O渐进表示法,这里就不再介绍了,忘记了的同学可以往上翻翻
递归
除外,递归
会建立额外的函数栈帧
O(1)
或 O(N)
眼看千遍,不如手过一遍,下面跟着我一起来看看试题,练练手吧!
//计算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;
}
答案:
O(N)
先看题目,这是一个迭代实现的斐波那契数列,没有使用递归
,直接看看创建的变量个数:
- fibArray
- (n+1) * sizeof(long long)
- i
共计申请了三块空间,其中第二块空间最大,为最高阶项,即
n + 1
,去除常数项,最终结果为O(N)
//计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{
if (N == 0)
return 1;
return Fac(N - 1) * N;
}
答案:
O(N)
递归的规则是先递出,再回归,如果中途遇到递归,继续递出
,因此在计算递归
的空间复杂度
时,计算的是每次递归调用的变量个数相加(所开辟的空间),也可以看作递归的深度
显然这里的递归深度是N
,开辟了N
个栈帧,每个栈帧使用了常数个空间,空间复杂度自然就是O(N)
了
你学会了吗?是不是感觉空间复杂度要比时间复杂度简单些?毕竟现在是大容量时代,内存都变得不值钱了,于是对空间的要求自然而然的变低了。
一般算法的常见复杂度类型如图所示
二分查找
logN
是真的强!有些题目中,对时间复杂度和空间复杂度是有要求的,比如下面这两个简单题,用来练手就很不错,动起来吧!关于这两题的题解,后续会发布的
10.25更新
两道题目的题解文章已发布,欢迎查看
C语言题解 | 消失的数字 &轮转数组
以上就是本次关于时间复杂度和空间复杂度的全部内容了,作为数据结构中的第一课,算是比较偏向于理论的部分,学起来也还比较简单,开胃菜嘛,等后面手撕顺序表、链表、二叉树
就爽了
如果你觉得本文写的还不错的话,期待留下一个小小的赞👍,你的支持是我分享的最大动力!
如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正
…
相关文章推荐
你真的了解时间复杂度吗
如何计算时间复杂度
时间复杂度计算 例题合集
我的函数应该返回给定数组范围内缺失的元素。所以我首先对数组进行排序并检查i和i+1之间的差值是否不等于1,我将返回缺少的元素。//GivenanarrayAsuchthat://A[0]=2//A[1]=3//A[2]=1//A[3]=5//thefunctionshouldreturn4,asitisthemissingelement.functionsolution(A){A.sort((a,b)=>{returnb<a;})varlen=A.length;varmissing;for(vari=0;i<len;i++){if(A[i+1]-A[i]>1){
我有一个像这样的对象{"status":"success","auth":{"code":"23123213","name":"qwertyasdfgh"}}我想将它转换为点符号(一级)版本,例如:{"status":"success","auth.code":"23123213","auth.name":"qwertyasdfgh"}目前我正在使用字段手动转换对象,但我认为应该有
迪杰斯特拉算法又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。以下是数据结构中关于迪杰斯特拉算法的操作(编程风格参考严蔚敏版数据结构)。头文件及宏定义#include<iostream>#include<stdio.h>usingnamespacestd;typedefcharVerTexType;typedefintA
这个问题在这里已经有了答案:关闭11年前。PossibleDuplicate:indexOfmethodinanobjectarray?我有一个遵循这种格式的javascript数组:vararrayName=[{id:"a",gender:"man",item:"stuff"},{id:"b",gender:"woman",item:"stuff"},{id:"c",gender:"man",item:"stuff"},{id:"d&
栈栈的概念:栈:栈顶和栈底压栈和出栈栈的实现用结构体自定义一个栈的数据类型初始化栈检测栈的容量是否充足(不充足进行扩容)入栈检测栈是否为空(为空返回非0结果,不为空返回0)出栈获取栈顶元素获取栈中有效元素个数销毁栈C语言实现栈的具体代码栈的概念:栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作,是操作受到限制的线性表,遵行后进先出LIFO(LastInFirstOut)的原则。简单理解就是一个一端封口,另一端没有
目录📖1.什么是二叉树?🌴2.满二叉树和完全二叉树 ⛳2.二叉树的性质🔥3.二叉树的创建与遍历3.1创建二叉树3.2前中后序遍历——递归和非递归🏹4.二叉树的实现1️⃣获取树中节点的个数2️⃣获取叶子节点的个数3️⃣获取第K层节点的个数4️⃣获取二叉树的高度5️⃣检测值为value的元素是否存在6️⃣判断两棵树是否相同【leetcod】7️⃣另一棵树的子树【leetcod】8️⃣翻转二叉树【leetcod】🔟平衡二叉树【leetcod】⏸二叉树的层序遍历二叉树的分层遍历【leetcod】Ὅ
我有一个工作面试即将到来,公司的核心技术之一是JavaScript。我被告知下一次面试将集中在JS数据结构上,这个术语在我的任何教育中都从未出现过。我花了一段时间在谷歌上试图找到更多关于它们的信息,我能遇到的最好的事情是thisWikipediapage.如您所知,项目列表很长,在我面试之前要研究的太多了。由于Wiki文章是通用的而不是特定于JS的,我知道那里的一些(大多数?)不适用于JS。关于主要数据结构是什么以及我应该把时间集中在什么方面,我可以获得一些帮助吗?我无法在Google上找到答案。我知道数组是我需要了解的主要内容之一。我应该准备好谈论的其他主要数据结构是什么?感谢您的帮
我正在一个涉及多项计算的财务系统中实现单元测试。其中一种方法,通过参数接收一个具有100多个属性的对象,并根据这个对象的属性,计算返回值。为了对该方法实现单元测试,我需要为该对象的所有内容填充有效值。所以...问题:今天这个对象是通过数据库填充的。在我的单元测试中(我使用的是NUnit),我需要避开数据库并为其创建一个模拟对象,以仅测试方法的返回值。我怎样才能用这个巨大的对象有效地测试这个方法?我真的需要手动填写它的所有100个属性吗?有没有一种方法可以使用Moq(例如)自动创建这个对象?obs:我正在为已经创建的系统编写单元测试。此时重写所有架构是不可行的。一百万!
这是我的第一个SO问题,与其说是“我该怎么做”,不如说是“最干净的方法是什么”,因为我看到了几种方法,但没有一种看起来非常对我很有吸引力。这个问题描述起来有点复杂。本质上,我有一个添加/编辑View,允许用户编辑某些对象的字段。这个对象非常复杂:它有一些字段,还有一个复杂对象的子列表。每个复杂对象大约有40个字段(主要是复选框、单选按钮和日期/时间)。我将其表示为一个选择列表:(来源:fortheloot.com)添加按钮会生成包含各个字段的对话框。问题来了。当用户接受对话框并关闭对话框时,我现在必须将这些数据存储在某个地方,以便用户可以在实际提交表单之前进一步编辑它或添加其他子项。最
一、C语言中计算数组长度大小C语言字符串长度的计算可以使用strlen(str);但是对于数组长度的大小却没有相关函数可以使用;C语言数组长度的大小可以使用:intmain(){intarr[]={1,2,3,4,5};intlength=sizeof(arr)/sizeof(int);printf("thelengthofarris%d\n",length);}二、在函数调用中计算数组的长度上述计算数组长度的方法在函数调用中不可使用,有bug;考虑下面代码:#include<stdio.h>voidtest(int*arr){intlength=0;length=sizeof(a
我有以下用于从Azurekey保管库获取secret的代码:publicstaticasyncTask<string>GetToken(stringauthority,stringresource,stringscope){varauthContext=newAuthenticationContext(authority);ClientCredentialclientCred=newClientCredential(...);//appid,appsecretAuthenticationResultresult=awaitauthContext.AcquireTokenAs
我有一个要求,我需要在日期字段上工作,所以要求是这样的我将该字段称为最短可能日期给日期加1如果最小可能日期恰好在添加1天后的周末(周六或周日),则显示下一个工作日,即周一如果可能的最短日期恰好是假日,则显示下一个工作日。(节假日1.1、1.5、3.10、25.12、26.12)如果最小可能日期恰好在加上1天后的周末(星期六或星期日),而后一天是假期,则显示下一个工作日。例如:+1天后,如果可能的最短日期是星期六,我们将不得不显示星期一。但如果星期一恰好是假期,那么我们必须显示星期二。我已经尝试通过多个if和else案例来解决上述问题,但只是想知道是否有任何通用且优雅的方法来解决这个问题
请建议哪个最适合获取执行程序集位置。Assembly.GetAssembly(typeof(NUnitTestProject.RGUnitTests)).Location或Assembly.GetExecutingAssembly().Location请建议哪个更好。我也可以使用GetEntryAssembly()吗? 最佳答案 这取决于你想要什么。Assembly.GetAssembly返回声明了type的程序集。Assembly.GetExecutingAssembly返回正在执行当前代码的程序集。Assembly.GetEnt
我有两个对象列表。List<object1>obj1=newList<object1>();List<object2>obj2=newList<object2>();我想这样做:obj2=obj2.Except(obj1).ToList();但是,通过阅读与我的类似的其他问题,我了解到除非我覆盖Equals,否则这是行不通的。我不想那样做,但是obj2和obj1都有一个字符串属性,足以判断它们是否相等。如果obj2.StringProperty等同于obj1.StringProperty那么可以认为两者相等。有什么方法可以使用Except
我似乎无法阻止WebAPI/JSON.NET在序列化对象时使用Newtonsoft.Json.PreserveReferencesHandling.Objects。换句话说,尽管使用了以下设置,但$id/$ref始终在序列化对象中使用:publicclassMvcApplication:System.Web.HttpApplication{protectedvoidApplication_Start(){WebApiConfig.Register(GlobalConfiguration.Configuration);}}publicstaticclassWebApiConfig{pub
我在VS2012上使用分析工具,发现clr.dll运行了很多时间。是垃圾收集吗?clr.dll能做什么?请告诉我。谢谢! 最佳答案 公共(public)语言运行时。它基本上是.NET的引擎 关于c#-.NetFramework上的clr.dll是什么,它有什么作用?,我们在StackOverflow上找到一个类似的问题: https://stackoverflow.com/questions/19698819/
因此,我正在启动一个新的.Net4.0项目,并将使用公共(public)API进行一些工作。我计划使用MicrosoftHttpClient类,所以我安装了最新稳定版本的Microsoft.Net.HttpNuGet包(版本2.2.13)。我正在查看同事放在一起的一些POC代码,也使用HttpClient的NuGet包并注意到有这样的代码:HttpClientclient=newHttpClient();HttpResponseMessageresponse=client.GetAync("/uri").Result;DomainTyperesult=response.
我是MVC的新手,我正在关注“AdamFreeman的PROASP.NETMVC4”。我目前正在研究它的第6章。我正在学习如何使用MVC4中的Ninject进行依赖注入(inject)。我已经按照书中的描述创建了应用程序。现在我不明白为什么会出现以下错误:该类型似乎没有实现microsoft.practices.servicelocation.iservicelocator这是我的Controller代码:publicclassHomeController:Controller{privateProduct[]products={newProduct{Name="Kayak
我确定我已经在框架的各种异常消息中看到了这一点。我从MSDN库中查看了以下页面,但找不到有关消息内容的太多指导:ExceptionThrowingErrorMessageDesignException.MessageProperty第一页中唯一可以解释它的部分是这段文字:Donotdisclosesecurity-sensitiveinformationinexceptionmessageswithoutdemandingappropriatepermissions.这是Dictionary<TKey,TValue>.Addmethod抛出的ArgumentExceptio
我想订购一个字符串列表,但列表中的一个字符串应始终位于开头且未排序。使用LINQ执行此操作的最简单方法是什么?//shouldbeorderedin:first,a,b,u,z:List<string>l={"z","u","first","b","a"};LINQ中没有prepend方法之类的,是吗? 最佳答案 l=l.OrderBy(i=>i!="first").ThenBy(i=>i).ToList();这里