在线问答5

这个屌丝很懒，什么也没留下！

热门标签

【数据结构】时间复杂度和空间复杂度_数据结构时间复杂度和空间复杂度

作者：在线问答5 | 2024-07-29 21:06:40

踩

数据结构时间复杂度和空间复杂度

数据结构开篇

接下来我们就开始数据结构的学习了，我们数据结构的学习分为两部分：一是初阶数据结构的学习，二是数据结构的学习。这里我们学习的是初阶数据结构，我们主要通过C语言来实现，在我们学习完初阶数据结构后会去学习C++,再转来学习高阶的数据结构。

一、算法效率

1.1 衡量一个算法的好坏

如何衡量一个算法的好坏？这是一个问题，我们以一个求斐波那契数列的函数来举例：


long long Fib(int N)
{
    if(N<3)
        return 1;
    else
        return Fib(N-1) + Fib(N-2)
}

这是我们之前求斐波那契数列三种方法中的一种——递归的求法。

这里我们发现，递归实现的方式十分简洁，但是这是对于我们来说简洁，那对于CPU呢，他的计算速度怎么样呢？这时我们就要采用一些判定方法来衡量这种方法到底好不好。

1.2 算法的复杂度

算法再编写成可执行程序后，运行时所耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

二、时间复杂度

2.1时间复杂度的相关概念

时间复杂度的定义：

在计算机科学中， 算法的时间复杂度是一个函数 ，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法 的时间复杂度。

即：找到某条基本语句与问题规模 N 之间的数学表达式，就是算出了该算法的时间复杂度。

2.2 大O的渐进表示法

大O符号：是用于描述函数渐进行为的数学符号。

推到大o阶的方法：

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

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

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

通俗点说，时间复杂度估算就是算该算法属于哪个量级.

2.3常见时间复杂度的计算

示例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);
}

F(N) = 2*N + 10 ;

则大O表示法则为：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(N+M)；

N远大于M：则为O(N);

M远大于N：则为O(M)；

M和N一样大：则为O(N)或O(M)；

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

这里O(1)不是表示1次，而是表示常数次；

示例4(冒泡排序)：
// 计算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;
 }
}
我们先算冒泡排序准确的时间复杂度

F(N)=N-1 + N-2 + N-3 +……+ 2 + 1

= $\frac{((N-1)+1)*(N-1))}{2}$ //等差数列公式

所以O( $N^{^{2}}$ )

另外：冒泡排序最好的情况为：O(N)

示例5(二分查找)：
// 计算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;
     else
         return mid;
 }
 return -1; 
}
最好的情况:O(1)

最坏的情况:找不到这个数或该数是最后一个数.

推导：

N/2/2/2/2……/2 = 1;

此时折半了多少次，就找了多少次。

假设折半了x次，

则2^x=N;

则X=log N (以2为底，通常省略)

大O阶表示法：O(logN)

示例6：


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

从N-->N-1-->N-2-->……-->1-->0 ；

则O(N)

示例7(递归斐波那契数列)：


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

三、空间复杂度

3.1 空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中额外占用存储空间大小的量度。(可理解为，为了实现这个算法而特定额外开辟的空间)

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时显示申请的额外空间来确定。

3.2常见空间复杂度的计算

示例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]);
                exchagae = 1;
            }
        }
    
        if (exchage == 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+1个空间，空间复杂度为 O(N)

示例3:
// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
    if(N == 0)
        return 1;
    return Fac(N-1)*N;
}
递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

示例4：
// 计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N) 
{
 if(N < 3)
     return 1;
 return Fib(N-1) + Fib(N-2);
}
时间是累积的，空间是不累计的，重复利用的，

所以斐波那契数列递归算法的空间复杂度:O(N)

四、常见的复杂度对比

一般算法常见复杂度如下:

五、复杂度OJ练习题

5.1.消失的数组

题目链接：面试题 17.04. 消失的数字 - 力扣（LeetCode）

这道题目有三种思路：

1.公式法:( 时间:O(N),空间O:(1))

因为数组nums包含从0到n的所有整数，我们可以将0-n的所有整数相加起来，再依次减去给定数组中的每个数，即可得出却失的那个数。
int missingNumber(int* nums, int numsSize){
    int temp=0;
    for (int i=0;i<numsSize+1;i++)
    {
        temp+=i;
    }
    for (int j=0;j<numsSize;j++)
    {
        temp-=*(nums+j);
    }
    return temp;
}

2. 对照法：( 时间:O(N),空间O:(N))

开辟一个Size大小的空间，初始化全为-1;然后将给定数组中的数放到对应下标的位子，再遍历一遍数组，找处仍然存放着-1的位置，返回其下标，则就是缺失的数字。


int missingNumber(int* nums, int numsSize)
{
    //开辟一个Size大小的空间
    int *p=(int*)malloc(sizeof(int)*(numsSize+1));
    //初始化为-1;
    for(int i=0;i<numsSize+1;i++)
    {
        *(p+i)=-1;
    }
    //将数放到malloc的数组中
    for(int j=0;j<numsSize;j++)
    {
        p[*(nums+j)]=*(nums+j);
    }
    //找到仍然为-1的那个下标
    for(int temp=0;temp<numsSize+1;temp++)
    {
        if (*(p+temp)==-1)
        {
            return temp;
        }
    }
    return 0;
}

3.异或法 ( 时间:O(N),空间O:(1))

根据异或的性质：1.相同的数异或为0；2.任何数与0异或都为0。这里我们用temp与0-n的整数都异或一遍，然后将temp异或数组中的数，哪个数没出现，则temp就等于那个数。
int missingNumber(int* nums, int numsSize){
    int temp=0;
    //异或0-n的数
    for (int i=0;i<numsSize+1;i++)
    {
        temp=temp^i;
    }
    //异或数组中的数
    for(int j=0;j<numsSize;j++)
    {
        temp=temp^(*(nums+j));
    }
    //剩下的这个就是没有出现过的数字
    return temp;
}

5.2 旋转的数组

题目的链接：189. 轮转数组 - 力扣（LeetCode）

该题目也有三种解法，但是第一种思路最简单的解法不能通过，因为执行效率过慢。

1.挨个右旋法(时间:O(N*K),空间:O(N))

这也是思路最简单的一种方法，在本地编译器中案例少的情况下是可以通过的，但是在力扣中因为时间复杂度过高无法通过。

根据传入的k进行一个一个右旋。1.先将第一个数据保存起来；2.然后将所有数据向前移动一个单位；3.再将数据插入到数组的最后位置。

2.创建新数组，直接存放旋转后的数据(时间:O(N),空间:O(N))

这种方式第一步：1.创建一个新数组，用来存放旋转后的数据；2.将数据放入旋转后应在的位置；3.将该数组拷贝到原数组中去。
void rotate(int* nums, int numsSize, int k){
 int newArr[numsSize];
    for (int i = 0; i < numsSize; ++i) {
        newArr[(i + k) % numsSize] = nums[i];
    }
    for (int i = 0; i < numsSize; ++i) {
        nums[i] = newArr[i];
    }
}

3.三步逆置法( 时间:O(N),空间O:(1))

这里我们就可以直接创建一个reverse函数，进行三次调用既可


void reverse(int*p,int start,int end)
{
    while(start<end)
    {
        int temp;
        temp=p[start];
        p[start]=p[end];
        p[end]=temp;
        start++;
        end--;
    }
}
void rotate(int* nums, int numsSize, int k){
            //除去多余的翻转
            k %= numsSize;
            reverse(nums,0,numsSize-k-1);
            reverse(nums+numsSize-k,0,k-1);
            reverse(nums,0,numsSize-1);
}

上面的习题可以帮你加强对时、空间复杂度的理解,希望本篇博客能对你有所帮助。

我们下期再见。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/在线问答5/article/detail/900577