@
目录
- 前言
- 算法效率
- 时间复杂度
- 样例1
- 样例2
- 样例3
- 样例4
- 样例5
- 样例6
- 递归的时间复杂度求解
- 空间复杂度
新的学习阶段又开始了,在更新完C语言后,博主将开始更新数据结构的知识了,说到数据结构想必大家都是知道其重要性吧.
嗯,废话不多说,那我们现在就开始谈谈数据结构吧~
什么是算法效率? 即
判断一个程序的相对好与坏的方法
.算法效率的测评主要有两种:
- 第一种: 时间复杂度(又称时间效率)
- 第二种: 空间复杂度(又称空间效率)
而由于现在科技的飞速发展,计算机的存储容量已经极大提高,
空间复杂度
并不是重点了,我们今天需要着重讲解的就是
时间复杂度
!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!敲黑板!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !! !!! !!!!
重要的事情一定要多说几遍,时间复杂度测的
!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!不是时间!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!
一个程序的执行时间完全会受到很多因素的影响,比如同样的程序,在不同的机器,执行的时间却不一定相同,所以说如果我们要用 时间的长短来评价一个程序的好坏这明显是不科学的,因此才提示时间复杂度的概念 :
算法中的基本操作执行次数
,而他的表示方法则是大O渐进表示法,即O(m) ,m是关于次数的表达式
请问函数
Func1
的时间复杂度是多少?
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² + 2N + 10;
所以用大O渐进表示法就是O(N² + 2N + 10),对吗???,先不回答,我们先看看下面:
| N | F(N) | N² |
|---|---|---|
| 1 | 13 | |
| 10 | 130 | 100 |
| 10210 | 10000 | |
| 1000 | 1002010 | 1000000 |
| 100020010 | 100000000 |
我们发现,随着N的逐渐增大,F(N)的值也逐渐增大,但是却也与N²的值非常接近,因此我们便可以不看尾数,即我们再用大O渐进表示法时候是不需要精确计算运行次数,而只是求个大概.
-
**下面是总结的大O表示原则:**
-
**用常数1取代运行时间中的所有加法常数。**
-
**在修改后的运行次数函数中，只保留最高阶项。**
-
**如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶**
-
所以
Func1
的时间复杂度是
O(N²)
,同时提醒一下哦,时间复杂度计算的是
在最坏情况下的哦
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);
}
经过分析可以得知,Func2的基本执行次数是:
F(N) = 2N + 10;
根据大O表示法原则第一条F(N)变成: F(n) = 2N + 1;
根据大O表示法原则第二条F(N)变成: F(n) = 2N;
根据大O表示法原则第三条F(N)变成: F(n) = N;
所以最终
时间复杂度是 : O(N)
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);
}
经过分析可以得知,Func3的基本执行次数是:
F(N) = M + N
根据大O渐进表示法原则,可以知道
时间复杂度为: O( M + N)
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
经过分析可以得知,Func4的基本执行次数是:
F(N) = 100
时间复杂度为: O(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;
}
}
经过分析可以得知,BubbleSort的基本执行次数是:
F(N) = n-1 + n-2 + n-3 + n-4 + ... + 3 + 2 + 1;
可以知道那是一个等差数列求和,所以F(N) = n*(n-1) / 2 = (1/2)N² - (1/2)N
按照大O表示法可以知道
时间复杂度为 O(N²)
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 | |
| 2 | N/2/2 |
| 3 | N/2/2/2 |
| ... | |
| x-2 | |
| x-1 | |
| x |
由此我们可以知道一个关系: 2^x = N,所以 x = ㏒₂(N), 即 F(N) = ㏒₂(N)
所以大O渐进表示法
时间复杂度为 O(㏒₂(N))
递归复杂度的计算公式为:
递归次数
*
每次递归里面的基本操作次数
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
递归次数: N
每次递归基本操作次数: 1
**所以F(N) = N*1; **
大O的渐进表示法
时间复杂度为:O(N)
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}
递归次数:
所以F(N) = 2^0 + 2^1 + 2^2 + ... 2^(n-2)
这是等比数列求和,所以F(N) = (1-2(n-2)) / (1-2) = 2^(n-2) - 1 = (1/4)*2^n - 1
所以大O表示法的
时间复杂度是 O(2^N)**
**
有人可能会说,这个是不准确的,的确,因为实际上这个次数是小于
2^(n-2) - 1
的,为什么呢,请看图:
即在中途后,次数就开始下降了,原因是有F(3)以下的数字先达到,就不再需要往下递归了.
但是即使这样,我们想一想按照这样真实的计算,最高次项是多少?? 其实还是2^N,所以
时间复杂度仍然为O(2^N)
!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!敲重点!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!
!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! 空间复杂度 !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!
计算的不是内存大小,而是程序每次执行,说临时开辟的变量数量
并且
时间复杂度是累积
的,但是
空间复杂度不累计
,并且空间复杂度的表示也是大O表示
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;
}
}
通过观察可以看见,程序开辟的变量数量只有3个,即常数个,所以
空间复杂度为 O(1)
long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long * fibArray =(long long *)malloc((n+1) * 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 ;
}
这个程序可以看见动态开辟了n+1个空间,所以
空间复杂度为O(N)
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
由于是递归,递归的空间复杂度计算类似. 等于
递归开辟的栈空间
每次递归开辟的变量数量
此题每次递归没有开辟变量,所以只计算
递归次数
,可知道连续递归了N次,所以
O(N
)
long long Fibonacci(size_t N)
{
return N < 2 ? N : Fibonacci(N-1)+Fibonacci(N-2);
}
还记得我们说过的,空间复杂度不累计吗????????????