百度商桥要怎么添加到网站,seo 网站推广入门,优化网站步骤,外贸简单网站建设#x1f308;个人主页#xff1a;聆风吟 #x1f525;系列专栏#xff1a;图解数据结构、算法模板 #x1f516;少年有梦不应止于心动#xff0c;更要付诸行动。 文章目录 一. ⛳️上期回顾二. ⛳️常见时间复杂度计算举例1️⃣实例一2️⃣实例二3️⃣实例三4️⃣实例四5… 个人主页聆风吟 系列专栏图解数据结构、算法模板 少年有梦不应止于心动更要付诸行动。 文章目录 一. ⛳️上期回顾二. ⛳️常见时间复杂度计算举例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 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通过计算分析发现基本操作递归了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)。 全文总结 本文通过大量实例讲解常见时间复杂和空间复杂度计算希望通过这些例子的讲解能够帮助你在以后的学习中能够更加灵活、精确的计算出一个程序的复杂度方便我们更快的寻找解决一个问题的最优的算法。 今天的干货分享到这里就结束啦如果觉得文章还可以的话希望能给个三连支持一下聆风吟的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是作者前进的最大动力
