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

推导大O阶方法：

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

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

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

2.2 计算一些常用算法的时间复杂度

根据上面的大O阶方法，计算一下Func1基本操作执行了多少次

下面可以看下这些练习题，分析练习使用大O的渐进表示法

练习1，计算Func2的时间复杂度

练习2，计算Func3的时间复杂度

练习3，计算Func4的时间复杂度

练习4，计算strchar的时间复杂度

练习5，计算Bubblesort的时间复杂度

练习6，计算Binarysearch的时间复杂度

练习7，计算Factorial的时间复杂度

练习8，计算斐波那契递归fibonacci的时间复杂度

所以递归的时间复杂度 = 递归的次数 * 每次递归执行的次数

常见的时间复杂度

O(N) O(N^2) O(logN) O(1)

2.3 计算一些常用算法的空间复杂度

空间复杂度是对一个算法在运行过程中
临时占用存储空间大小的量度，计算的是变量个数

时间是累计的，空间是不累计的

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

下面看几个例题

练习1，计算Bubblesort的空间复杂度

练习2，计算Fibonacci的空间复杂度

练习3，计算Factorial的空间复杂度

3.对复杂度有要求的算法练习题

在有些算法练习题中，会对复杂度有一些要求，所以在我们做题时就要，注意算法的设计

下面看一下力扣中的两个题

1.链接面试题 17.04. 消失的数字 – 力扣（LeetCode） (leetcode-cn.com)

int missingNumber(int* nums, int numsSize){
    int x=0;
    //跟数组中的值异或
    for(int i=0;i<numsSize;++i)
    {
        x^=nums[i];
    }
    //再跟[0，N]之间数字异或
    for(int j=0;j<numsSize+1;++j)
    {
        x^=j;
    }
    return x;
}

2.链接 189. 轮转数组 – 力扣（LeetCode） (leetcode-cn.com)

void Reverse(int* nums, int left, int right){
    while(left<right)
    {
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        ++left;
        --right;
    }
}
void rotate(int* nums, int numsSize, int k){
    if(k>=numsSize)
    {
        k%=numsSize;
    }
    Reverse(nums, numsSize-k, numsSize-1);
    Reverse(nums, 0, numsSize-k-1);
    Reverse(nums, 0, numsSize-1);

}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/91287.html