【数据结构】复杂度
算法的复杂度
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
在计算 机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
时间复杂度
时间复杂度的定义:在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。每个算法是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
/请计算一下Func1中++count语句总共执行了多少次? N^2+2N+10
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);
}
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O渐进表示法。
大O的渐进表示法
大O符号(Big O notation) :是用于描述函数渐进行为的数学符号。
推导大0阶方法:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大0阶。
使用大O的渐进表示法以后，Func1的时间复杂度为:O(N2)
例一：
// 计算Func2的时间复杂度? 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);
}
例二：
// 计算Func3的时间复杂度? O(N+M),如果给出M远大于N，可写为O(M)
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);
}
例三：
//计算Func4的时间复杂度? O(1)
void Func4(int N){
int count =0;
for (int k = 0; k < 100; ++k){
++count;
}
printf("%d\n", count);
}
有些算法的时间复杂度存在最好、平均和最坏情况:
- 最坏情况:任意输入规模的最大运行次数(上界)
- 平均情况:任意输入规模的期望运行次数
- 最好情况:任意输入规模的最小运行次数(下界)例如:在一个长度为N数组中搜索一个数据x
在实际中一般情况关注的是算法的最坏运行情况
例四：
// 计算strchr的时间复杂度?O(N)
const char * strchr ( const char * str, int character );
while(*str){
if(*str==character)
return str;
++str;
}
例五：
计算BubbleSort的时间复杂度?最好O（N）,最坏O（N^2)
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;
}
例六：
// 计算BinarySearch的时间复杂度?
//最好O（1）
//最坏O（logN）（2^k=N,k=log2（N),以2为底可以简化)
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 = mid+1;
else if (a[mid] > x)
end = mid-1;
else
return mid;
}
return -1;
}
例七：
//计算阶乘递归Fac的时间复杂度? O（N）
long long Fac(size_t N)
if(0==N)
return N;
return Fac(N-1)*N;
}
例八：
// 计算斐波那契递归Fib的时间复杂度? O（2^N）
long long Fib(size_t N){
if(N<3)
return 1;
return Fib(N-1)+Fib(N-2);
}
等比数列+常数（缺失）
常见复杂度
空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度
空间复杂度不是程序占用了多少bytes的空间，空间复杂度算的是变量的个数
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法
注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定
例1：冒泡排序的空间复杂度
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;
}
例2:计算Fibonacci的空间复杂度
O(N)
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long * fibarray = (1ong long *)ma11oc((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;
}
例3：计算阶乘递归Fac的空间复杂度
O(N)
//建立N+1层栈帧，每层为O（1）
long long Fac(size_t N){
if(N==0)
return 1;
return Fac(N-1)*N;
}
例4：计算斐波那契递归Fib的时间复杂度
O(N)
long long Fib(size_t N){
if(N<3)
return 1;
return Fib(N-1)+Fib(N-2);
}
时间不可重复利用，空间可以
例题1：
- 方法1：排序＋二分查找
冒泡排序：O(N^N)
qsort快排：O(N*logN),二分查找可忽略不计 - 方法2：异或
相异为1，相同为0
0跟任何数异或都等于这个数
A^ B^ B = A
以[3,0,1]为例
3，0，1分比与0到3内所有整数异或，最后只剩下2
0^ 1^ 2^ 3^ 3^ 0^ 1 = 0^ 0^ 1^ 1^ 2^ 3^ 3 = 2 (异或满足交换律）
时间复杂度：O（N）
- 方法3：公式计算
等差数列求和公式
0~n求和 - 数组内所有元素之和
O（N）
例题2：
-
方法1：一步一步移
将最后一个数字保存起来，再将前几个数字一次向后移动一位，以此类推
O（N^N) -
方法2：翻转法
前n-k个逆置，后k个逆置，整体逆置
以[1,2,3,4,5,6,7]为例：
4，3，2，1，5，6，7
4，3，2，1，7，6，5
5，6，7，1，2，3，4
时间复杂度O（N）
空间复杂度O（1）
-
方法3：空间换时间
开一个数组，把后k个拷贝到前面，再把n-k个拷贝到后面
空间复杂度：O（N）
时间复杂度：O（N）
原文地址：https://blog.csdn.net/2402_87467998/article/details/144481427
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！