文章目录
1.时间复杂度
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。
一个算法所花费的时间与其中语句的执行次数成正比例。所以算法中的基本操作的执行次数，为算法的时间复杂度。
大O用来表示程序执行次数的
大O的渐进法表示
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
void Func1(int N)
{
int count = 0;//执行次数为1
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;//1.count执行次数为N^2
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;//2.count执行次数为2*N
}
int M = 10;
while (M--)
{
++count;//count执行次数为10次
}
printf("%d\n", count);//执行次数为1
}
所以此函数执行次数的关系式为：
N总=1+n^2+2
n+10+1=2
n+12+n*n;
当n趋于无穷大时n^2是2*n和12的高阶无穷小，所以N总的大小不用考虑这两项，此外高阶无穷小前的系数在n->无穷的时候不考虑。
保留最高阶项，忽略最高阶前的系数
所以此函数的时间复杂度为O(n^2)
常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3) k次方阶,指数阶O(2^n)。
注意O(1)表示常数次，这个常数次可以很大
如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
eg:
int main()
{
int i = 0;
for (i = 0; i < 1000000000; i++)
{
;
}
return 0;
}
循环次数虽然多，但这只是很大的常数，所以时间复杂度仍为O（1）
最好、平均和最坏情况
例如：查找算法
最好情况：查找一次就找到了。
最坏情况：查找了N次查找到了。
平均情况：（1+N）/2
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
具体函数分析
一：
void Func2(int N) {
int count = 0;//执行1次
for (int k = 0; k < 2 * N ; ++ k) {
++count; }//执行2*N
int M = 10;//执行1次
while (M--) {
++count; }//执行10次
printf("%d\n", count);//执行一次
}
所以执行次数函数为
N总=2*n+12;
大O法只保留最高阶，且忽略最高阶前的系数
所以Func2（）的时间复杂度为O(N)
二：
void Func3(int N, int M) {
int count = 0;//执行1次
for (int k = 0; k < M; ++ k) {
++count; }//执行M次
for (int k = 0; k < N ; ++ k) {
++count; }//执行N次
printf("%d\n", count);//执行1次
}
所以执行次数的函数为：
N总=m+n+2;
注意：在这里不能确定m,n，有两个未知数会影响执行次数，且这两个未知数的阶数相同，所以不能轻易省略。
所以大O表示Func3（）函数的时间复杂度为O(M+N)
三：
void Func4(int N) {
int count = 0;//执行1次
for (int k = 0; k < 100; ++ k) {
++count; }//执行100次
printf("%d\n", count);
}
所以执行次数的函数为：
N总=11
算法的执行时间不随着问题规模n的增加而增长
所以大O表示Func4（）函数的时间复杂度为O（1）
四：
char* strchr(char *s, char c)
{
while(*s != '\0' && *s != c)
{
++s;//执行N次，与传入函数的字符串有关
}
return *s==c ? s : NULL;
}
所以函数strchar（）执行次数的表达式为:
最好为1次，最坏为N次
大O法表示为其最坏的情况.
所以strchr函数的时间复杂度为O（N）
五：
//冒泡排序法
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的数组首元素地址，以及数组长度
exchange的作用为记录数组是否交换，
1.如果exchange的值在经历了第一次循环后还是0，表明该数组已经有序，不需要交换，直接返回。只是经过了一次查找数组
所以可以知道算法最好情况用大O法表示为O(N)；
2.在经历了第一次循环N-1次后end减少，下一次循环次数变为N-2次。
所以所以函数BubbleSort（）执行次数的表达式为:
(N-1)+(N-2)+(N-3)…+1=(1+N-1)*(N-1)/2=N(N-1)/2
大O法表示为其最坏的情况.
大O法只保留最高阶，且忽略最高阶前的系数O(N^2)
六：
int BinarySearch(int* a, int n, int x) {//二分查找法找数字
assert(a);
int begin = 0;
int end = n-1;
while (begin < end) {
int mid = begin + ((end-begin)>>1);//找中间位置
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid;
else
return mid; }
return -1; }
由上图我们可以知道查找一次，N被分成2份。查找二次,N被分成4份，
设查找的f(x)次,此时N被分成2^f(x)份。
2^f(x)=N,解得f(x)=logN，这个就是它的执行次数。
所以用大O法表示为O(logN)
七：
long long Factorial(size_t N) {
return N < 2 ? N : Factorial(N-1)*N; }
//这个代码是递归求阶乘
递归的时间复杂度=递归次数*每次递归过程中函数的执行次数
阶乘递归的次数是从N到1，共有N次。每一次递归过程中函数执行次数是1次（一句三目操作符）
所以Factorial()的时间复杂度为O(N*1)=O(N);
注意：
如果还是递归N次，但每一次递归都有一个
for(int i=0;i<N;i++){}；这时每次递归过程中函数执行次数为N次
时间复杂度变为O(N*N)=O(N^2)
八：
long long Fibonacci(size_t N) {
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);斐波那契数列
}
为了方便举例子，这里先从N=4的时候说起
每一次函数的执行次数为1
所以大O表示O(2^N*1)