[数据结构与算法]21 11 11数据结构学习总结（时间复杂度与空间复杂度）

一 时间复杂度

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

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

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

void Func1(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);
}

O(N+M)

void Func2(int N)
{
    int count=0;
    for(int k=0;k<100;k++)
    {
        count++;
    }
    printf("%d\n",count);
}

O(1)

void Func3(int N)
{
    int count=0;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            count++;
        }
    }
    for(int i=0;i<2*N;i++)
    {
        count ++;
    }
    int M=10;
    while(M--)
    {
        count ++;
    }
    printf("%d\n",count);
}

O(N*N)

const char* strchr(const char* str,char character)
{
    while(*str!='\0')
    {
        if(*str==character)
            return str;
        str++;
    }
    return NULL;
}

O(N)

有些算法复杂度存在最好，平均，最差情况，此时按最差情况算

冒泡的时间复杂度为O(N*N)? （N为数字个数）

二分法查找的时间复杂度为0?? （N为数字个数）

常见的时间复杂度：O(N*N) O(N) O(logN) O(1)

二 空间复杂度

空间复杂度不计算空间，计算变量个数

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])
            {
                exchange=1;
            }
        }
        if(exchange==0)
            break;
    }
}

O(1)

时间复杂度是累计的，空间复杂度不累计

循环走了n次，重复利用的是一个空间

long long Factorial(size_t N)
{
    return N<2? N:Factorial(N-1)*N;
}

O(N)

调用时建立栈帧，返回时销毁栈帧

三 复杂度在算法的意义

校园招聘的笔试算法题和面试中会考察对复杂度的计算和理解

例题：

数组nums包含0到n的所有整数，但缺了一个，请编写代码找出缺失的整数，在O(N)时间内完成：

思路一：

排序，时间复杂度不符合，最快O(N*logN)

思路二：

把0到N加到一起，计为ret1，再把数组中所有数加到一起，计为ret2，ret1-ret2就是我们要找的数

#include<stdio.h>
int missingNumber(int* nums,int numsSize)
{
    int ret1=0;
    for(int i=1;i<=numsSize;i++)
    {
        ret1=ret1+i;
    }
    int ret2=0;
    for(int j=0;j<9;j++)
    {
        ret2=ret2+nums[j];
    }
    return ret1-ret2;
}
int main()
{
    int nums[10]={0,1,2,3,4,5,7,8,9};
    int numsSize=9;
    int x=missingNumber(nums,numsSize);
    printf("%d\n",x);
    return 0;
}

思路三：

数组中数依次与0--N中所有数异或，最后剩下的数据为缺少的数据

#include<stdio.h>
int missingNumber(int* nums,int numsSize)
{
    int x=0;
    for(int i=0;i<numsSize;i++)
    {
        x^=nums[i];
    }
    for(int j=0;j<numsSize+1;j++)
    {
        x^=j;
    }
    return x;
}
int main()
{
    int nums[10]={0,1,2,3,4,5,7,8,9};
    int numsSize=9;
    int x=missingNumber(nums,numsSize);
    printf("%d\n",x);
    return 0;
}