临沂网站建设培训,天津装修公司排名前十名,西安建站平台,网站推广 英文文章目录1. 算法效率1.1 什么是算法1.2 算法的好坏2. 时间复杂度2.1 什么是时间复杂度2.2 时间复杂度的计算方法2.3 大O的渐进表示法2.4 常见时间复杂度计算举例3. 空间复杂度4. 常见复杂度对比1. 算法效率
1.1 什么是算法
目前普遍认可对算法的定义是#xff1a;算法是解决…
文章目录1. 算法效率1.1 什么是算法1.2 算法的好坏2. 时间复杂度2.1 什么是时间复杂度2.2 时间复杂度的计算方法2.3 大O的渐进表示法2.4 常见时间复杂度计算举例3. 空间复杂度4. 常见复杂度对比1. 算法效率
1.1 什么是算法
目前普遍认可对算法的定义是算法是解决特定问题求解步骤的描述在计算机中表现为指令的有限序列并且每个指令表示一个或多个操作。 大白话就是计算的方法通过该方法可以达到我们预期的计算结果。
1.2 算法的好坏
最近“九转大肠”在网络上十分火爆小伙在制作过程中故意的保留了“原始风味”令评委十分“粪怒”。那为什么同样是“九转大肠”评价却如此不一样呢评委点评看三个方面做菜的材料、做菜的时间、菜的味道三者缺一不可。
算法也是如此在保证计算能出我们预期的结果的前提下还需考虑效率。 即算法在编写成可执行程序后运行时需要耗费时间资源和空间内存资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量即时间复杂度和空间复杂度。 小贴士: 时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 2. 时间复杂度
2.1 什么是时间复杂度
一个算法所花费的时间与其中语句的执行次数成正比例总语句执行次数记为T(n)。在一般情况下算法中基本操作重复执行的次数是问题规模n某个函数f(n)算法的时间量度记作T(n) O(f(n))。它表示随着问题规模n的增大算法执行时间的增长率和f(n) 增长率相同称为算法的渐进时间复杂度简称时间复杂度。
2.2 时间复杂度的计算方法
一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但如果每个程序都需要上机测试就会很麻烦。 我们只需计算出算法中的基本操作的执行次数即可。 例如
//计算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执行的基本操作次数 F(N) N2 2*N 10
在这里我们并不需要计算出准确的次数只需要算出该函数是是属于哪个量级。即找出函数式中对结果影响最大的那个。假设这里的N为无限大那么后面的 2*N 10对结果的影响就微乎其微。 所以不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。
2.3 大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。
推导大O阶方法
用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
用大O的渐进表示法以后那么Func1的时间复杂度为 O(N2)。 另外有些算法的时间复杂度存在最好、平均和最坏情况。 例如要用在长度为N的数组中查找某个数据
最好的情况第一次就找到最坏的情况第N次才找到平均情况N/2次找到
那我们该取哪种情况呢举个例子约了一个好朋友出来吃饭预定时间1200。
按预定时间到达1200最坏情况那么就只能吃个饭。都提前一小时到1100最好情况先逛逛街吃个饭、最后还能散散步。提前半小时到1130平均情况吃饭-散步-带回。
那么我们肯定是说12点到嘛如果12点之前到就会有额外的惊喜如果直接告诉最好的情况实际效果可能就没那么好。 所以时间复杂度在实际情况下关注的是算法运算最坏情况。
2.4 常见时间复杂度计算举例
O(1)
// 计算Func1的时间复杂度
void Func1(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}基本操作执行了100次是一个确定的值通过推导大O阶的方法无最高阶项常数用1表示。即时间复杂度为O(1)。
O(n)
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
}基本操作递归了N次最高阶项是N通过推导大O阶的方法只保留最高阶项。即时间复杂度为O(n)。
O(n2)
// 计算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*N-1/2次时间复杂度看最坏情况再通过推导大O阶的方法最高阶项为N2。即时间复杂度为O(n2)。
O(logN)
// 计算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 mid1;else if (a[mid] x)end mid-1;elsereturn mid;}return -1;
}这里是一个二分查找的算法基本操作执行情况是1次最坏情况是O(logN)次 ps:logN在算法分析中表示底数是2每次查找减一半即时间复杂度为O(logN)。 小贴士 在理论上二分查找是一个非常牛的算法例如在10000个数据中它最坏情况下大概10次就找出来了如果用冒泡排序则最坏需要查找 100002次这二者的差别十分之大。但是二分查找有一个前提就是数据序列必须是一个有序序列这就带来了很大的局限性。 3. 空间复杂度
空间复杂度也是一个数学表达式是一个对算法在运行过程中临时占用存储空间大小的量度算的是变量的个数同时也使用大O渐进表示法。 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 示例1
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
}在这里调用了N次Fac阶乘函数每调用一次就创建一个函数栈帧那个就开辟了N个内存空间即空间复杂度为O(n)。
示例2
// 计算斐波那契递归Fib的空间复杂度
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}该算法的时间复杂度为O(2n)那么额外申请的空间也是 2n 吗 这里的递归并不是我们想象中一层一层往下面调用。 通过这两个样例的比较我们可以总结出时间复杂度和空间复杂度的特性
时间是一去不复返的不可重复利用空间用了需要返还可以重复利用
4. 常见复杂度对比
