安徽住房和建设网站,山东百度推广,网站建设找谁做,网赌网站怎么建设时间复杂度与空间复杂度详解#x1f996; 一、算法效率1.1 如何衡量一个算法的好坏1.2 算法的复杂度 二、时间复杂度2.1 时间复杂度的定义2.2 大O的渐进表示法2.3 如何记录表示算法复杂度 三、空间复杂度3.1 空间复杂度的定义3.2 小试牛刀 一、算法效率
1.1 如何衡量一个算法… 时间复杂度与空间复杂度详解 一、算法效率1.1 如何衡量一个算法的好坏1.2 算法的复杂度 二、时间复杂度2.1 时间复杂度的定义2.2 大O的渐进表示法2.3 如何记录表示算法复杂度 三、空间复杂度3.1 空间复杂度的定义3.2 小试牛刀 一、算法效率
1.1 如何衡量一个算法的好坏 我一直有个问题算法到底如何比较如何衡量一个算法的好坏 我的理解 思路巧妙神来之笔 枯燥的代码却带着无限的智慧也是这智慧让程序员在学习过程中一次次惊呼妙哉此法妙哉所以对我而言一个奇巧的思路是竞赛衡量的一个标准主观感受 时间、空间资源利用 一串好的算法代码不一定是简洁的但一定是空间、时间资源占用少的。
1.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);
}Func1 执行的基本操作次数
N 10 F(N) 130N 100 F(N) 10210N 1000 F(N) 1002010
根据上述带入尝试我们不难得出Func1执行的基本操作次数是下面这个函数表达式 F ( N ) N 2 2 ∗ N 10 数学表达式 F(N) N^2 2*N 10数学表达式 F(N)N22∗N10数学表达式 在实际计算中我们并不会计算精准的次数一般采取估算量级所以我们会使用大O的渐进表示法
2.2 大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。
推导大O阶方法
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中只保留最高阶项(高数极限思想)。
3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后Func1的时间复杂度为 O ( N 2 2 ∗ N 10 ) − − O ( N 2 ) O(N^2 2*N 10)--O(N^2) O(N22∗N10)−−O(N2)
总结一下 大O渐进表示法主要是记录复杂度量级去掉了那些对结果影响不大的项。
2.3 如何记录表示算法复杂度
一个算法运行过程往往有三种衡量记录情况
最坏情况 任意输入规模的最大运行次数(上界)
平均情况 任意输入规模的期望运行次数
最好情况 任意输入规模的最小运行次数(下界)
所以可以描述一个算法的复杂度范围来表示算法的复杂度范围但实际中我们往往采用最坏的情况来表示记录一个算法的复杂度我也喜欢因为每一次运行都只会有惊喜
三、空间复杂度
3.1 空间复杂度的定义 空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度(额外空间大小) 。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。
注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
3.2 小试牛刀
实例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;}
}实例1我们必须明确的是空间复杂度记录的是额外的临时变量空间大小因此我们再看实例1的时候只会计算end、exchange、i等临时变量大小即可。不用计算数组a开辟的空间大小。所以这里空间复杂度就是O(1);
实例2
// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if(n0)return NULL;long long * fibArray (long long *)malloc((n1) * 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;
}实例2这里相当于malloc创建了n1个临时空间大小因此也非常简单这里空间复杂度也就是O(N)。
这就是最基本的。空间复杂度相较于时间复杂度要简单很多通常不是O(N)就是O(1)。
