作者:coraft | 来源:互联网 | 2023-09-25 18:44
本文主要介绍关于数据结构,c语言,开发语言的知识点,对【C语言数据结构——复杂度】和【c语言时间复杂度和空间复杂度】有兴趣的朋友可以看下由【龙兆万】投稿的技术文章,希望该技术和经验能帮到你解决你所
本文主要介绍关于数据结构,c语言,开发语言的知识点,对【C语言数据结构 —— 复杂度】和【c语言时间复杂度和空间复杂度】有兴趣的朋友可以看下由【龙兆万】投稿的技术文章,希望该技术和经验能帮到你解决你所遇的相关技术问题。
c语言时间复杂度和空间复杂度
1. 算法效率 1.1 如何衡量一个算法的好坏
如果衡量一个算法的好坏呢?比如我们有一段关于斐波那契数列的代码:
long long Fib(int N) {
if (N <3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
递归实现方式代码是非常简洁的,但是简洁并不代表高效率。因为其中包含了太多重复运算,大家可以自己图解这个算法,这里不再赘述。
1.2 算法的复杂度
算法再编写成可执行程序后,运行时需要耗费时间资源河空间资源。因此衡量一个算法的好坏,一般时从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期,计算机的存储容量很小,所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经大道了很高的高度,所以我们如今已经不需要再特别关注一个算法的空间复杂度了。
2. 时间复杂度 2.1 时间复杂度的概念
时间复杂度的定义:再计算机科学中,算法的时间发杂度是一个函数(数学函数),它定量描述了该算法的运行时间。
但是这个运行时间并不是我们主观意识的时间,因为在不同的机器上,同一段代码的运行时间是不一样的。比如我的处理器可以吊打银河系,而你的处理器打开 WPS 都费劲,那么同一段代码在分别在这两台机器上跑的时间肯定是不一样的。所以,算法中的基本操作的执行次数,为算法的时间复杂度。
那么如何找到算法的时间复杂度?即找到某校基本语句与问题规模 N 之间的数学表达式。例如说我们有以下代码:
// 请计算一下Func1中++count语句总共执行了多少次?
void Func1(int N)
{
int count = 0;
for (int i = 0; i
我们可以看到,Func1 函数的基本操作次数为 F(N)=N^2+2*N+10 ,并且有:
N=10 F(N)=130N=100 F(N)=10210N=1000 F(n)=1002010
但是在实际中计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要计算大概执行次数,那么这里我们使用大 O 的渐进表示法。
2.2 大 O 的渐进表示法
大O 符号:描述函数渐进行为的数学符号。
推导大 O 阶方法:
用常数 1 取代运行时间中的所有加法常数
在修改后的运行次数函数中,只保留最高阶项
如果最高阶项存在且不是 1 ,则出去这个项目相乘的常数
使用大 O 的渐进表示法以后,Func1 的时间复杂度为:O(N^2)
N=10 F(N)=100N=100 F(N)=10000N=1000 F(N)=1000000
通过上面我们会发现大 O 的渐进表示法去掉了那些对结果影响不大的项,简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏的情况:
最坏情况:任意输入规模的最大运行次数平均情况:任意输入规模的期望运行次数最好情况:任意输入规模的最小运行次数
例如说:在一个长度为 N 的有序数组中查找一个元素 x
最好情况:1 次找到
最坏情况:N 次找到
平均情况: N/2 次找到
在实际中一般情况关注的是算法的最坏运行情况,所以数组中查找元素的时间复杂度为 O(N) 。
2.3 常见时间复杂度计算举例
实例1:
// 计算Func2的时间复杂度?
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);
}
对于 Func2 ,我们可以计算的大概执行次数为 2*N+10 ,但是我们用大 O 的渐进表示法,可以省略掉一些项,那么最终的时间复杂度为 O(N) 。
实例2:
// 计算Func3的时间复杂度?
void Func3(int N, int M) {
int count = 0;
for (int k = 0; k
对于 Func3 ,可以计算大概的基本执行次数为 M+N ,两项都不能被忽略,所以用大 O 的渐进表示法,可以得出时间复杂度为 O(M+N) 。
实例3:
// 计算Func4的时间复杂度?
void Func4(int N) {
int count = 0;
for (int k = 0; k <100; ++k)
{
++count;
}
printf("%d\n", count);
}
对于 Func4 ,可以计算基本执行次数为 100 ,是一个常数,所以用大 O 的渐进表示法为 O(1) 。
实例4:
// 计算strchr的时间复杂度?
const char* strchr(const char* str, int character);
以前我们介绍过 strstr 这个函数,那么对于 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 a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
这是一个冒泡排序算法。我们需要注意,计算时间复杂度时不能只看循环,这种做法是肤浅的、错误的。我们应该关注算法的内核。就拿这个冒泡算法来说,我们通过图解来表达清楚冒泡排序的核心:
可以看到,最好的情况就是执行 N 次(不是 1 次原因是即使不进行元素交换,此算法也会对数组遍历检查)。最差的情况就是计算 1、2、3……N-2、N-1 这个等差数列之和,即 (N-1)*N/2 ,那么要表示时间复杂度,就要用大 O 的渐进表示法,即去除影响不大的项,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)
end = mid - 1;
else
return mid;
}
return -1;
}
这是一个二分查找的算法,我们来具体分析一下此算法的时间复杂度。我们通过最坏的角度去分析:
所以这个二分查找的算法的时间复杂度为 O(logN) 。
实例7:
// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N) {
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
对于函数递归,我们只需要关心函数被调用几次即可。那么对于求阶乘的递归算法来说,函数被调用了 N 次,所以时间复杂度为 O(N) 。
实例8:
// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N) {
if (N <3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
现在我们来分析文章开头提到的斐波那契数列的递归算法。此算法的时间复杂度为 O(2^N) 。
那么大家看到这个算法的时间复杂度是非常高的,这就证明了这个算法的效率非常低。例如说我们要求斐波那契数列的第 40 个数字,那么它的计算量为 2^40 ,可想而知,效率非常低下。
3. 空间复杂度
空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时(额外)占用存储空间大小的量度。
空间复杂度不是程序占用了多少字节空间,而是变量(空间)的个数。即使想要计算程序占用了多大空间也没有意义。
空间复杂度计算规则与时间复杂度一样,都使用大 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 a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
我们要注意,计算空间复杂度是要计算变量(空间)的个数。因为所占空间数为常数,所以空间复杂度为 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;
}
这个算法就非常简单了。占用的空间与参数 n 有关,所以空间复杂度为 O(N) 。
实例3:
// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N) {
if (N == 0)
return 1;
return Fac(N - 1) * N;
}
可以明确的看到,Fac 函数被调用 N+1 次,每次调用都开辟一个栈帧,而这个栈帧又是常数。但是调用几次又参数 N 决定,所以空间复杂度为 O(N) 。
补充:
在刚才的计算中,可以发现我们并没有把形参的所占空间给算进去。这里需要注意的是,函数的形参是完成算法的条件,并不是额外开辟的一个临时空间。
4. 复杂度的 oj 练习
消失的数字
题解:
int missingNumber(int* nums, int numsSize)
{
int sum=0;
for(int i=0;i<=numsSize;i++)
{
sum+=i;//求出 0~n 范围的和
}
int tmp=0;
for(int i=0;i
轮转数组
题解1,以空间换时间:
void rotate(int* nums, int numsSize, int k)
{
int* arr=(int*)calloc(numsSize,sizeof(int));
int size=k%numsSize;
memcpy(arr,nums+numsSize-size,size*sizeof(int));
memcpy(arr+size,nums,(numsSize-size)*sizeof(int));
memcpy(nums,arr,numsSize*sizeof(int));
free(arr);
arr=NULL;
}
题解2,三步翻转法:
//三步翻转
void reverse(int* nums, int left, int right)
{
while (left = numsSize)
k %= numsSize;
reverse(nums, 0, numsSize - k - 1);
reverse(nums, numsSize - k, numsSize - 1);
reverse(nums, 0, numsSize - 1);
}
本文《C语言数据结构 —— 复杂度》版权归龙兆万所有,引用C语言数据结构 —— 复杂度需遵循CC 4.0 BY-SA版权协议。