【数据结构】常见复杂度习题详解 ------ 习题篇

---

📋前言

🏠 个人主页：@聆风吟的个人主页

🔥系列专栏：本期文章收录在《数据结构初阶》，大家有兴趣可以浏览和关注，后面将会有更多精彩内容！

⏰寄语：少年有梦不应止于心动，更要付诸行动。
🎉欢迎大家关注🔍点赞👍收藏⭐️留言📝
🌈作者留言：本文从上篇文章《算法、时间复杂度和空间复杂度详解 》中剥离出来的，由于详解和题目放在一起篇幅过长，不利于大家更好吸收知识点，特此将其剥离出来。

---

一. ⛳️前篇回顾

上篇文章我们主要学习了：

1. 算法的定义：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
2. 算法的特性：有穷性、确定性、可行性、输入、输出。
3. 算法的设计要求：正确性、可读性、健壮性、高效率和低存储量需求。
4. 算法的度量方法：事后统计方法、事前分析估算方法。
5. 推导大O阶
6. 时间复杂度
7. 空间复杂度

    你对以上的内容是否还能够全部回忆起来呢？如果你对某部分还有欠缺，请跳转该篇文章《算法、时间复杂度和空间复杂度详解 》进行复习，再配合着下面习题对时间复杂度和空间复杂度进行巩固。预计明天将会更新数据结构新文，大家抓紧时间在复习下前面知识。

---

二. ⛳️常见时间复杂度计算举例

1️⃣实例一

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

解析：实例1基本操作执行了2N+10次，根据大O阶的推导方法很容易得出：Func1的时间复杂度为O(N)。

2️⃣实例二

// 计算Func2的时间复杂度？
void Func2(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);
}

解析：实例二基本操作执行了M+N次，根据大O阶的推导方法得出：

• 如果题目没有表明 M 和 N 的大小，Func2的时间复杂度为O(M + N)；
• 如果题目明确表明 M 远大于 N ，则 N 的变化对时间复杂度的影响不大，Func2的时间复杂度为O(M)；
• 如果题目明确表明 N 远大于 M ，则 M 的变化对时间复杂度的影响不大，Func2的时间复杂度为O(N)。
• 如果题目明确表明 M 和 N 一样大，则O(M + N)等价于O(2M)或O(2N)，Func2的时间复杂度为O(M) 或 O(N) ；

3️⃣实例三

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

解析：实例3基本操作执行了100次，根据大O阶的推导方法很容易得出：Func3的时间复杂度为O(1)。

4️⃣实例四

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );

解析：首先我们先来介绍一下库函数strchr作用：在str指向的字符数组中查找是否包含字符characte。因此实例4的基本操作执行最好1次，最坏N次。根据时间复杂度一般看最坏，strchr的时间复杂度为O(N)。

5️⃣实例五

// 计算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;}
}

解析：本题是冒泡排序函数，冒泡排序的思想是：假设数组中有 n 个元素，第一趟执行将会执行 n-1 次交换，将一个元素排好序。第二趟将会执行 n-2 次交换，将将一个元素排好序…依次类推。排好所有元素需要执行 n-1 次，每趟交换的次数分别为(n - 1)，(n-2)，(n-3)，… ，(2)，(1)。由此可知，实例5基本操作执行最好n-1次（即数组已经排好序，只需要执行一趟排序判断数组是否已经有序），最坏执行了( n*(n-1) )/2次（即将所有趟交换的次数相加，可以直接使用等差数列求和），通过推导大O阶方法+时间复杂度一般看最坏，BubbleSort的时间复杂度为O(N^2)。

6️⃣实例六

// 计算BinarySearch的时间复杂度？
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;elsereturn mid;}return -1;
}

解析：本题是二分查找函数，每次查找将会将范围缩放一半。因此实例6基本操作执行最好1次，最坏O(logN)次。根据时间复杂度一般看最坏，BinarySearch时间复杂度为 O(logN) 。

7️⃣实例七

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

解析：本题是一个简单的递归调用， 实例7通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。

8️⃣实例八

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}

解析：本题是一个双递归。实例8通过计算分析发现基本操作递归了2ⁿ，Fib的时间复杂度为O(2^n)。

---

三. ⛳️常见空间复杂度计算举例

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;}
}

解析： 实例1使用了常数个额外空间，分别是[ end，exchange，i ]。根据大O阶的推导方法很容易得出，BubbleSort空间复杂度为 O(1)

2️⃣实例二

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
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;
}

解析：实例2动态开辟了N+1个空间，根据大O阶的推导方法很容易得出，Fibonacci空间复杂度为 O(N)。

3️⃣实例三

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

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

---

四. ⛳️总结

     本文通过大量实例讲解常见时间复杂和空间复杂度计算，希望通过这些例子的讲解能够帮助你在以后的学习中能够更加灵活、精确的计算出一个程序的复杂度，方便我们更快的寻找解决一个问题的最优的算法。

     今天的内容就到这里了，你对今天的内容是否有所掌握？如果还有疑问的话请在评论区里多多提问，大家可以一起帮你解决，让我们共同进步。创作不易，如果对你有用的的话点个赞支持下作者，你们的支持是作者创作最大的动力。关注我不迷路，让我们下期不见不散✋✋。