北京网站建设net2006,模板网站搭建,个人网站开发制作教程,wordpress前台修改专栏#xff1a;数据结构 个人主页#xff1a;HaiFan. 专栏简介#xff1a;开学数据结构#xff0c;接下来会慢慢坑新数据结构的内容#xff01;#xff01;#xff01;#xff01; 时间复杂度前言1.算法效率1.1如何衡量一个算法的好坏1.2算法的复杂度2.时间复杂度2.1大… 专栏数据结构 个人主页HaiFan. 专栏简介开学数据结构接下来会慢慢坑新数据结构的内容 时间复杂度前言1.算法效率1.1如何衡量一个算法的好坏1.2算法的复杂度2.时间复杂度2.1大O的渐进表示法2.2实例1.常数次2.O(MN)3.O(N)4.logN前言 什么是数据结构
数据结构是计算机存储组织数据的方式指相互之间存在一种或多种特定关系的数据与元素的集合
什么是算法
算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为 输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果
1.算法效率
1.1如何衡量一个算法的好坏
比如以下的算区间和的代码
#include iostream
using namespace std;
const int N 1e5 10;
int a[N];
int s[N];
int main()
{int n, m;cin n m;for (int i 1; i n; i){cin a[i];}while (m--){int l, r;cin l r;int sum 0;for (int i l; i r; i){sum a[i];}cout sum endl;}for (int i 1; i n; i){s[i] s[i - 1] a[i];}return 0;
}实现这个区间和很简单代码也很简洁但是简洁一定好吗如何衡量代码的好与坏呢
1.2算法的复杂度
举个例子 小兰写了一个冒泡排序 小张写了一个快速排序 小兰和小张执行同一组数据小兰花了3s小张花了5s。 这样能说明冒泡排序的效率比快速排序的效率高吗 答案是不能的。 算法在编写成可执行程序后运行时需要耗费时间资源和空间资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。
时间复杂度主要是用来衡量一个算法的运行快慢
空间复杂度主要是用来衡量一个算法运行所需要的额外空间。
2.时间复杂度
时间复杂度在计算机科学中算法的时间复杂度是一个函数他定量描述了该算法的运行时间一个算法执行所耗费的时间从理论上说是不能算出来的只有把程序放在机器上跑起来才知道但是每个代码都需要进行一次测试吗虽然可以但会很麻烦所以就有了时间复杂度这个分析方式一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。
即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度
#include iostreamusing namespace std;int main()
{int n;cin n;int ret 0;for (int i 1; i n; i){for (int j 1; j n; j){ret;}}for (int i 1; i n; i){ret;}int m 100;while (m--){ret;}cout ret;return 0;
}那么这个代码中的ret共执行了多少次呢
在代码开始有一个双重循环这个时候ret就执行了n*n次后面又有一个循环这个时候ret执行了n次最后又执行了m次ret
我们可以推出ret的次数
F(n) n*n n m
m是一个常数表达式可以写成
F(n) n * n n 100
n 10 F(n) 10010100210n 100 F(n) 100*1001001001200
依次类推当n特别大的时候得到的函数值也是特别大的。 实际中我们计算时间复杂度时其实不一定要算执行次数只需要计算大概执行次数这就需要使用大O的渐进表示法
2.1大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。
推导大O阶方法
用1来取代运行时间中的所有加法常数在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是1则去除与这个项目相乘的常数得到的结果就是大O阶
使用大O阶表示上面代码的时间复杂度
O(N^2)
大O的渐进表示法去掉了那些对结果影响不大的项。 有些算法的时间复杂度存在最好平均和最坏情况
最坏情况任意输入规模的最大运行次数(上界)
平均情况任意输入规模的期望运行次数
最好情况任意输入规模的最小运行次数(下界) 例如在一个长度为N数组中搜索一个数据x
最好情况1次找到
最坏情况N次找到
平均情况N/2次找到 在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N) 2.2实例
1.常数次
#include iostreamusing namespace std;int main()
{int cnt 0;for (int i 1; i 100; i){cnt;}cout cnt;return 0;
}这个代码非常的简单时间复杂度也很好求因为就一个循环并且是常数次所以时间复杂度就是O(1) O(1)不是代表一次而是常数次 2.O(MN)
#include iostreamusing namespace std;int main()
{int N;int M;cin N M;for (int i 0; i N; i){;}for (int i 0; i M; i){;}return 0;
}这个代码是两个循环第一个循环次数是N次第二个循环次数是M次那么时间复杂度就是O(MN)。 值得注意的是如果M和N相等那么时间复杂度就是O(N) 如果不相等就要写成O(NM) 3.O(N)
#include iostreamusing namespace std;int main()
{int N;cin N;int cnt 0;for (int i 0; i N * 2; i){cnt;}cout cnt;return 0;
}循环次数是N*2时间复杂度就是O(N)把N前面的2给省略。
4.logN
二分查找又叫折半查找
int l 0;
int r n - 1;
int mid l r 1;while (l r)
{mid l r 1;if (a[mid] x){r mid;}else{l mid 1;}
}二分时间复杂度最好的情况就是第一次就找到了O(1)
最坏情况O(logN)(以2为底) 在以2为底的对数中一般可以写成logN其他的不能省略 二分的最坏情况时间复杂度为什么是logN呢
因为每次查找都会缩小区间查找几次就除多少个2
N/2/2/2…/21
2^xN
xlogN
