建个个人网站一年多少钱,品牌营销的重要性,江苏网站建设网站排名优化,公司网站建设申请单1. 时间复杂度
1.1 概念
简而言之#xff0c;算法中的基本操作的执行次数#xff0c;叫做算法的时间复杂度。也就是说#xff0c;我这个程序执行了多少次#xff0c;时间复杂度就是多少。
比如下面这段代码的执行次数#xff1a;
void Func1(int N)
{int count 0;for…1. 时间复杂度
1.1 概念
简而言之算法中的基本操作的执行次数叫做算法的时间复杂度。也就是说我这个程序执行了多少次时间复杂度就是多少。
比如下面这段代码的执行次数
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) N^2 2*N 10
在这里两层for循环的次数是N^2第二个for循环的次数是2*Nwhile循环的次数是10 所以这个算法中的基本操作次数就是 N^2 2*N 10。
那我们的时间复杂度就是这个吗其实不是的。实际上我们在计算时间复杂度的时候我们并不一定要计算精确的执行次数而只需要大概执行次数。
这又是为什么呢
当N 10的时候F(N) 130
当 N 100 的时候F(N) 10210
当 N 1000 的时候F(N) 1002010
我们发现当N趋于无穷大的时候对F(N)影响最大的是N^2这就跟我们在数学里找极限一样抓大头找影响最大的一项用影响最大的一项来表示我们的时间复杂度
这种表示方法我们称作大O的渐进表示法。
1.2大O的渐进表示法
大O符号Big O notation用于描述函数渐进行为的数学符号。
基本执行次数用大O阶方法表示的规则
1. 如果执行次数中出现加法常数无论多大只要是常数用1来代替。
2. 如果执行次数是多项式执行次数只保留最高阶项最高次项
3. 如果最高阶项存在且不是1舍去系数。
4.经过123操作得到的结果就是大O阶表示。 所以我们上面的F(N) N^2 2*N 10 用大O阶表示就是 O(N^2)。
1.3 最好平均最坏情况
有些算法的时间复杂度是存在最好平均最坏情况的。
1.最好情况基本操作次数的最小值
2.平均情况期望的基本操作次数
3.最坏情况基本操作次数的最大值
但是在实际中我们都是用最坏情况来表示时间复杂度
1.4 时间复杂度例题
1.4.1 例题1
void Func2(int N)
{int count 0;for (int k 0; k 2 * N ; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}
答案O(N)
基本执行次数是2 * N 10用大O阶表示为O(N)
1.4.2 例题2
void Func3(int N, int M)
{int count 0;for (int k 0; k M; k){count;}for (int k 0; k N ; k){count;}printf(%d\n, count);
}
答案O(MN)
基本执行次数是MN次由于有两个未知数M和N所以大O阶表示为O(MN)
1.4.3 例题3
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}
答案O(1)
基本执行次数是100次用大O阶表示为O(1)
1.4.4 例题4
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;}
}
答案O(N^2)
基本操作次数是(n-1)(n-2)(n-3)....321 ((n 1) * n) / 2
最好情况就是遍历一次就排序成功基本操作次数是n-1大O阶表示是O(N)
最坏情况就是全部遍历完基本操作次数是((n 1) * n) / 2大O阶表示为O(N^2)
时间复杂度一般看最坏情况为O(N^2)
大O表示为O(N^2)
1.4.5 例题5
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;
}
答案O(log N)
这个算法是二分查找
最好情况是查找一次为O(1)
最坏情况是begin end 了只剩了一个元素我们可以设循环的次数是x一次循环我们是砍掉了一半的数组元素那到最后没有元素了说明n / 2^x 1
所以x log n(以2为底)。时间复杂度的大O阶表示就是O(logN)。
我们规定以2为底的对数函数写成 log N
1.4.6 例题6
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
}
答案O(N)
基本操作次数这个函数一共递归了N次时间复杂度就是O(N)
1.4.7 例题7
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}
答案O(2^N)
基本操作次数这个函数递归了1248... 是一个不完整的等比数列在N3之后不会递归但是不影响整体的趋势可以忽略不计这个等比数列的和是2^n - 1
所以大O阶表示为O(2^n)
2.空间复杂度
2.1概念
空间复杂度指的是临时占用存储空间大小的量度需要注意的是空间复杂度并不是程序占了多少个字节的空间因为没有什么太大意义所以空间复杂度指的是新创建的变量个数
空间复杂度计算规则和时间复杂度基本一致用大O阶渐渐表示法。
注意⚠️⚠️⚠️
1. 计算空间复杂度时一般不需要考虑函数的形式参数。空间复杂度主要关注的是算法执行过程中所占用的额外空间而函数的形式参数在函数调用时会被压入调用栈中属于函数调用过程中的内存分配并不计入空间复杂度的计算。
2. 递归算法在每次递归调用时需要维护函数调用栈而函数调用栈会占用额外的内存空间所以其空间复杂度为递归所使用的堆栈空间的大小。
2.2 空间复杂度例题
2.2.1 例题1
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;}
}
这个冒泡排序临时创建的变量分别是 end exchange 和 i 一共三个是常数个。
所以空间复杂度用大O阶表示为O(1)
2.2.2 例题2
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;
}
这个算法我们直接看新创建的变量是fibArray这个数组是动态开辟的一个数组开辟了n1个空间还有个i变量一共是n2个变量。
用大O阶表示为O(n)
2.2.3 例题3
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
}
首先我们要明确的是这是一个函数递归调用 我们函数递归一共要递归N次共创建新的栈空间N个
所以空间复杂度为O(N)
2.2.4 例题4
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}
此时的空间复杂度是多少呢 O(2^N) 还是O(N)
我们画图来说明 我们来看这个函数的递归调用并不是同时进行的而是先调用左边的左边调用完了最下面Fib2往回销毁空间之后才去调用Fib1也就是在这个时候才开辟Fib1的空间 蓝色箭头代表从Fib3到Fib2先开辟Fib2的栈空间当调用结束的时候这段空间就要销毁于是就有了红色的箭头代表销毁Fib2的空间销毁之后我们才开始调用Fib1绿色箭头代表调用Fib1此时就要开辟Fib1的空间要知道的是我们刚刚销毁一个栈空间现在又要开辟一个栈空间所以空间是被重复利用的也就是黄色的箭头Fib1的空间跟Fib2的空间是同一块空间。
所以我们真正开辟的空间只有从FibN到Fib2这一段其他的调用函数都是在重复利用栈空间的过程。
所以空间复杂度是O(N)
总结时间是累积的一去不复返 空间是可以重复利用的。
3.常见复杂度的对比
常数阶O(1)5201314线性阶O(N)3N1平方阶O(N^2)2N^2 3N 1对数阶O(logN)3log(2)N 2NlogN阶O(NlogN)2N3Nlog(2)N 1立方阶O(N^3)3N^32N^2N1指数阶O(2^N)2^N
O(1) O(log n) O(n) O(nlogn) O(n^2) O(n^3) O(2^n) O(n!) O(n^n)
