数据结构 -＞ 时间复杂度和空间复杂度的计算（做题助推器）

文章目录

void Func1(int N)
{
     int count = 0;
     for (int i = 0; i < N ; ++ i)//每次执行下面for循环N次，N则N次循环就执行N^2次
     {
         for (int j = 0; j < N ; ++ j)
         {
             ++count;
         }
     }
     for (int k = 0; k < 2 * N ; ++ k)//2*N次
     {
         ++count;
     }
     int M = 10;//10次
     while (M--)
     {
         ++count;
     }
     printf("%d\n", count);
}

那么真实的执行次数是N^2+2N+10,但是实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次 数，那么这里我们使用大O的渐进表示法。

运算规则：

1 、用常数 1 取代运行时间中的所有加法常数。

2 、在修改后的运行次数函数中，只保留最高阶项。

3 、如果最高阶项存在且不是 1 ，则去除与这个项目相乘的常数。得到的结果就是大 O 阶。

3 .?常见时间复杂度计算举例

案例1：

// 计算Func2的时间复杂度？
void Func2(int N)
{
     int count = 0;
     for (int k = 0; k < 2 * N ; ++ k)//2*N
     {
         ++count;
     }
     int M = 10;
     while (M--)//10
     {
         ++count;
     }
     printf("%d\n", count);
}

准确的是2*N + 10，但是大O的渐进表示法去掉了那些对结果影响不大的项，则这个代码的时间复杂度为O(N)

案例2：

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
     int count = 0;
     for (int k = 0; k < M; ++ k)//M
     {
         ++count;
     }
     for (int k = 0; k < N ; ++ k)//N
     {
         ++count;
     }
     printf("%d\n", count);
}

时间复杂度的表示就是可以多个未知数的，所以Func2函数的时间复杂度是O（M+N）但是如果题目有说：

比如：

M远远大于Nze为O（M）

如果是说M和N差不多大就相当于2M，时间复杂度就为O（M）或O（N）。

案例3：

// 计算Func4的时间复杂度？
void Func4(int N)
{
     int count = 0;
     for (int k = 0; k < 100; ++ k)//100
     {
         ++count;
     }
     printf("%d\n", count);
}

O（100）但是没有这种表示，还记得这个吗？

1、用常数1取代运行时间中的所有加法常数。

// 计算BubbleSort的时间复杂度？//冒泡排序
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;
     }
}

案例6：

// 计算BinarySearch的时间复杂度？//2分查找
int BinarySearch(int* a, int n, int x)
{
     assert(a);
     int begin = 0;
     int end = n;
     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;
}

分析：

案例7：

// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N)
{
     return N < 2 ? N : Factorial(N-1)*N;
}

分析：

每次调用函数，执行一次，递归调用函数N次，每次递归运算3次，整体准确是O（3N），大O（渐进法）就是O（N）。

1. 实例 1 基本操作执行了 2N+10 次，通过推导大 O 阶方法知道，时间复杂度为 O(N)

2. 实例 2 基本操作执行了 M+N 次，有两个未知数 M 和 N ，时间复杂度为 O(N+M)

3. 实例 3 基本操作执行了 10 次，通过推导大 O 阶方法，时间复杂度为 O(1)

4. 实例 4 基本操作执行最好 1 次，最坏 N 次，时间复杂度一般看最坏，时间复杂度为 O(N)

5. 实例 5 基本操作执行最好 N 次，最坏执行了 (N*(N+1)/2 次，通过推导大 O 阶方法 + 时间复杂度

一般看最坏，时间复杂度为 O(N^2)

6. 实例 6 基本操作执行最好 1 次，最坏 O(logN) 次，时间复杂度为 O(logN) ps ： logN 在算法分析

中表示是底数为 2 ，对数为 N 。有些地方会写成 lgN 。（建议通过折纸查找的方式讲解 logN 是怎么计算出来的）

7. 实例 7 通过计算分析发现基本操作递归了 N 次，时间复杂度为 O(N) 。

复杂度对比：

4.??常见空间复杂度的计算

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用 了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计 算规则基本跟实践复杂度类似，也使用大O渐进表示法。

案例1：

// 计算BubbleSort的空间复杂度？
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的空间复杂度？
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 ;
}

分析：

案例3：

// 计算阶乘递归Factorial的空间复杂度？
long long Factorial(size_t N)
{
     return N < 2 ? N : Factorial(N-1)*N;
}

分析：

实例答案及分析：

1. 实例 1 使用了常数个额外空间，所以空间复杂度为 O(1)

2. 实例 2 动态开辟了 N 个空间，空间复杂度为 O(N)

3. 实例 3 递归调用了 N 次，开辟了 N 个栈帧，每个栈帧使用了常数个空间。空间复杂度为 O(N)