数据结构与算法——算法时间复杂度

妖狐艹你老母 2023-10-10 14:54 11阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击免费注册和我一起刷题吧][Link 2]

**文章目录**

1. 大O记法

2. 推导大O阶方法

3. 常数阶

4. 线性阶

5. 对数阶

6. 平方阶

7. 分析时间复杂度

7.1func1的时间复杂度

7.2 func2的时间复杂度

7.3 binarySearch的时间复杂度

7.4 阶乘递归factorial的时间复杂度

7.5 斐波那契递归fibonacci的时间复杂度

7.6 bubbleSort的时间复杂度

--------------------

## 1. 大O记法 ##

判断一个算法好不好，只通过少量的数据是不能做出准确判断的

T（n）= O（f(n)）

在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度就是算法的时间量度，记为T（n）= O（f(n)）

它表示某个算法，随着问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。f(n）为问题规模n的某个函数

这样用O（）来体现算法时间复杂度的记法称为大O记法

显然，在一般情况下，随着n的增大，T（n）增长最慢的算法为最优算法

## 2. 推导大O阶方法 ##

> 1.用常数1取代运行时间中的加法常数
> 
> 2.修改后的运行次数函数中，只保留最高阶项
> 
> 3.去掉最高阶项的系数（如果系数不为1）

这样就得到了大O阶

接下来是常见的大O阶

## 3. 常数阶 ##

//执行一次
            int sum = 0,n=10;
            //执行一次
            sum =1+n;
            //执行一次
            System.out.println(sum);

运行次数f(n)=3

根据我们的推导方法，第一步就是把常改为1，在保留最高阶项发现它没有最高阶项，所以它的时间复杂度是O（1）

再者，如果sum=1+n；这个语句有十句，则会执行12次。事实上，无论n为多少，两者的差异就是3次和12次，与n的大小是无关的，不会随着n的变大而发生变化，执行时间恒定的算法，我们称为具有O（1）的时间复杂度，又叫常数阶

## 4. 线性阶 ##

线性阶的循环结构会复杂很多。关键是分析循环结构的运行情况

for (int i = 0; i < n; i++) {
                // 时间复杂度为O（1）的程序步骤序列
    }

循环时间复杂度为O（n），因为循环体中的代码要执行n次

## 5. 对数阶 ##

int count = 1;
            while(count <n){
                count = count*2;
                //时间复杂度为O（1）的程序步骤序列
            }

由于每次count\*2以后，就距离n更近了，当多少个2相乘以后大于n，就会退出循环

由2^x=n得到x=log2(n)，所以这个循环的时间复杂度为O（logn）

## 6. 平方阶 ##

看一个循环嵌套

for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //时间复杂度为O（1）的程序步骤序列
                }
            }

内循环为O（n），对于外循环，不过是内部时间复杂度为O（n）的语句在循环n次，所以时间复杂度为O（n^2）

如果循环次数改为m，时间复杂度就变为O（m\*n）

## 7. 分析时间复杂度 ##

下面我们看几段代码分析一下时间复杂度

### 7.1func1的时间复杂度 ###

// 计算func1的时间复杂度？
            void func1(int N) {
                int count = 0;
                for (int k = 0; k < 2 * N ; k++) {
                    count++;
                }
                int M = 10;
                while ((M--) > 0) {
                    count++;
                }
                System.out.println(count);
            }

基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N)

### 7.2 func2的时间复杂度 ###

// 计算func2的时间复杂度？
    void func2(int N) {
    int count = 0;
    for (int k = 0; k < 100; k++) {
    count++;
    }
    System.out.println(count);
    }

基本操作执行了100次，通过推导大O阶方法，时间复杂度为 O(1)

### 7.3 binarySearch的时间复杂度 ###

// 计算binarySearch的时间复杂度？
    int binarySearch(int[] array, int value) {
                int begin = 0;
                int end = array.length - 1;
                while (begin <= end) {
                    int mid = begin + ((end-begin) / 2);
                    if (array[mid] < value)
                        begin = mid + 1;
                    else if (array[mid] > value)
                        end = mid - 1;
                    else
                        return mid;
                }
                return -1;
            }

基本操作执行最好1次，最坏 log2(n)次，时间复杂度为 O(log2(n)) ps： og2(n)在算法分析中表示是底数 为2，对数为N，有些地方会写成lgN。(因为二分查 找每次排除掉一半的不适合值,一次二分剩下：n/2 两次二分剩下：n/2/2 = n/4)。即n/(2^x),x=logn

### 7.4 阶乘递归factorial的时间复杂度 ###

// 计算阶乘递归factorial的时间复杂度？
    long factorial(int N) {
    return N < 2 ? N : factorial(N-1) * N;
    }

递归的时间复杂度=递归次数\*每次递归之后执行的次数

基本操作递归了N次，时间复杂度为O(N)

### 7.5 斐波那契递归fibonacci的时间复杂度 ###

// 计算斐波那契递归fibonacci的时间复杂度？
    int fibonacci(int N) {
    return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }

参考一下斐波那契数的递归图

![2bee56d26f1d4a60b5522399009a9d60.png][]

分析发现基本操作递归了2^n 次，时间复杂度为O( 2^n)

### 7.6 bubbleSort的时间复杂度 ###

// 计算bubbleSort的时间复杂度？
    void bubbleSort(int[] array) {
                for (int end = array.length; end > 0; end--) {
                    boolean sorted = true;
                    for (int i = 1; i < end; i++) {
                        if (array[i - 1] > array[i]) {
                            Swap(array, i - 1, i);
                            sorted = false;
                        }
                    }
                    if (sorted == true) {
                        break;
                    }
                }
            }

基本操作执行最好N次，最坏执行了(N\*(N-1))/2次，通过推导大O阶方法+时间复杂度一般看最坏，时间 复杂度为 O(N^2)

> “ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！

![ced485cbb11e458d81a746890b32cf3f.gif][]

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[2bee56d26f1d4a60b5522399009a9d60.png]: https://img-blog.csdnimg.cn/2bee56d26f1d4a60b5522399009a9d60.png