数据结构常见复杂度习题详解 习题篇,天勤数据结构习题

文章目录 前言一. ⛳️前篇回顾二. ⛳️常见时间复杂度计算举例1️⃣实例一2️⃣实例二3️⃣实例三4️⃣实例四5️⃣实例五6️⃣实例六7️⃣实例七8️⃣实例八 三. ⛳️常见空间复杂度计算举例1️⃣实例一2️⃣实例二3️⃣实例三 四. ⛳️总结

前言

个人主页聆风吟的个人主页

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

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

一. ⛳️前篇回顾

上篇文章我们主要学习了

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

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

二. ⛳️常见时间复杂度计算举例 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基本操作执行了2N10次根据大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);}

解析实例二基本操作执行了MN次根据大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 r );

解析首先我们先来介绍一下库函数strchr作用在str指向的字符数组中查找是否包含字符。因此实例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通过计算分析发现基本操作递归了2nFib的时间复杂度为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使用了常数个额外空间分别是[ endexchangei ]。根据大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动态开辟了N1个空间根据大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)。

四. ⛳️总结

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

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