好看的网站的导航怎么做,人才网招聘官方网,上海人才招聘官网2022,天津建设工程信息网官网首页1.时间复杂度的定义
在计算机科学中#xff0c;算法的时间复杂度是一个函数#xff0c;它定量描述了算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比列#xff0c;算法中的基本操作的执行次数#xff0c;为算法的时间复杂度
例1#xff1a;
计算Func1…1.时间复杂度的定义
在计算机科学中算法的时间复杂度是一个函数它定量描述了算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比列算法中的基本操作的执行次数为算法的时间复杂度
例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 i 0; i 2 * N; i){count;}int M 10;while(M--){count; }printf(%d\n, count);
}
Func1的基本操作次数F(N) N^2 2 * N 10来分析一下是为什么
首先可以看到这段代码有三个循环
第一个是由两个for内外嵌套组成每次循环N次执行了N次即N N N.....N * N N^2 次
第二个循环执行了 2*N 次
第三个循环执行了 10 次
如果每个时间复杂度都要这么表示的话那太复杂了所以我们只取最大量级来表示这段代码的时间复杂度
当N 10时F(N) 130
当N 20时F(N) 10210
当N 30时F(N) 1002010
当我们的N取无穷大时 2 * N 10这两个项对结果的影响已经不大了可以忽略不计所以说只需要取N^2来表示它的时间复杂度就可以了
所以这段代码Func1的时间复杂度为: O(N ^ 2) 2.大O的渐进表示法
大O符号(Big O notation)是用于描述函数渐进行为的数学符号
推导大O阶方法 1.用常数1来取代运行时间中的所有加法常数 2.在修改后的运行次数的函数中只保留最高阶项 3.如果最高阶存在且不是1则去除与这个项目相乘的常数得到的结果就是大O阶 通过上面一个例子我们可以发现大O渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数 我们来计算几道代码的时间复杂度
例1
void Func2(int N)
{int count 0;for(int i 0; i 2 * N; i){count;}int M 10;while(M--){count; }printf(%d, count);
}
F(N) 2 * N 10
去掉与最高阶相乘的常熟和10使用大O渐进法表示法该段代码的时间复杂度为O(N)
例2
void Func3(int M, int N)
{int count 0;for(int i 0; i M; i){count;}for(int j 0; j N; j){count;}printf(%d\n, count);
}
使用大O渐进法表示法该段代码的时间复杂度为O(N M)
因为M和N是未知的所以不能去掉它们两个任意一个
如果N大于M则可以去掉M反之可以去掉N相等可任取M和N中任何一个
例3
void Func4(int N)
{int count 0;for(i 0; i 100: i){count;}printf(%d\n, count);
}
F(N) 100
执行了100次但是我们用1来表示
使用大O渐进法表示法该段代码的时间复杂度为O(1)
注这里的1表示代表1次而是常数次 3.时间复杂度的最好最坏和平均情况
另外有些算法的时间复杂度存在最好平均最坏情况
最坏情况任意输入规模的最大运行次数(上界)
平均情况任意输入规模的期望运行次数
最好情况任意输入规模最小运行次数(下界)
例4
char* strchr(const char * str, int character)
{while(*Str){if(*str character){return str;}str;}return NULL;
}
例如在一个长度为N的数组中找一个数据x
最好情况1次找到
平均情况N/2次找到
最坏情况N次找到
在实际情况中一般关注的是算法的最坏运行情况所以该段代码的时间复杂度为O(N)
例5
void BubbleSort(int *a, int n)
{assert(a);for(int end n; end 1; --end){for(int i 1; i end; i){if(a[i - 1] a[i]){int tmp a[i];a[i] a[i 1];a[i 1] tmp;}}}
}
最好情况O(N)
最坏情况将两个for循环跑满
外循环为n时内循环循环n - 1次 然后按顺序n - 2, n-3, ....., 3, 2, 1通过判断可以知道这是一个等差数列所以它的总和就为n(n - 1 1)/2 n^2*1/2 即最坏情况O(N^2)
使用大O渐进法表示法去掉常数该段代码的时间复杂度为O(N^2)
例6
在数组有序的情况下可以使用二分法折半查找
int binarysearch(int *aint n, int x)
{int begin 0;int end n - 1;while(begin end){int mid begin ((end - begin)1);if(a[mid] x){end a[mid] - 1;}else if(a[mid] x){begin a[mid] 1;}else{return mid;}}return -1;
}
最好情况O(1)
最坏情况区间缩放到一个值要么找到要么找不到假设N为数组个数x是最坏查找次数N每次除2就等于查找一次折半查找多少次就除多少个2
N/2/2/2..../2 1, 因为n为int所以最小二分到12^x N 即x logNlog在时间复杂度中表示以2为底所以最坏情况O(logN)
例7
long long fac(size_t N)
{if(N 0)return 1;elsereturn fac(N - 1) * N;
}
使用大O渐进法表示法该段代码的时间复杂度为O(N)
例8
long long Fib(int n)
{if(n 3){return 1;}else{return Fib(n - 1) Fib(n - 2);}
}
最好情况O(1) 可以观察到该递归的方式为等差数列我们用求和公式可以得出2^(N-1)-1
最坏情况用大O渐进表示法O(2^N)
总结以上时间复杂度O(1)O(logN)O(N)O(N^2)O(N^3)O(2*N)
