数据结构Part II:时间复杂度以及空间复杂度

大家好,这次给大家带来的是我的新的专栏:Java语言实现的数据结构。数据结构是一门特别重要的学科,难度较高。IT届大佬常说:只有你学会了数据结构,你才算得上是一个中高等级的程序员。所以,我会竭尽所能帮助大家学习数据结构。之前的Java专栏因为时间原因会慢慢继续更新的,只不过时间较慢,慢工出细活😏

👀QQ:162196770

👀微信:PRIDE_Xu_

👀Gitee:https://gitee.com/jialebihaitao

👀上一篇博客传送门:https://blog.csdn.net/m0_53117341/article/details/124329352

👀文章专栏:
https://blog.csdn.net/m0_53117341/category_11774151.html
👀B站:建设中,以后会考虑在B站上讲解一些知识点等等

👀拿好你的入场券,我们要开始入场了!

入场券

1、如何衡量一个算法的好坏?

1.1 时间复杂度

  1. 如果我们想要通过计时的方式统计程序运行时间,这明显是不行的,因为不同设备执行代码速度是不同的,代码的执行是与机器的硬件、软件以及配置相关的!
  2. 时间复杂度主要衡量的就是一个算法的运行速度。

1.2 空间复杂度

  1. 空间复杂度主要衡量一个算法所需要的额外空间

2、时间复杂度

2.1 概念

一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

所以计算时间复杂度问题的切入点就是寻找执行次数最多的语句

2.2 大O的渐进表示法

先举个栗子:

	// 请计算一下func1基本操作执行了多少次?
    void func1(int N){
        int count = 0;
        for (int i = 0; i < N ; i++) {
            for (int j = 0; j < N ; j++) {
                count++;
            }
        }
        for (int k = 0; k < 2 * N ; k++) {
            count++;
        }
        int M = 10;
        while ((M--) > 0) {
            count++;
        }
        System.out.println(count);
    }

image-20220421113804985

通过分析,我们可以得到:

image-20220421115934565

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法

2.3 推导大O阶方法

  1. 用常数1取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

我们来把每一个小点剖析一下:

image-20220421120515106

所以刚才那个例子的时间复杂度为O(n^2)

😀😬😁😂😆😅😄😃😇😉😊🙂😌😋☺️🙃😍😘🥰😗😝😜😚😙😛🤑🤪🤣🤩😎🤓🧐🤗😏😶😐🤭🙄😒😑🤫🤔🤨😳

另外有些算法的时间复杂度存在最好、平均和最坏情况:

下面通过一个栗子分析一下这三种情况:

从N个数据里面找x,就分为三种情况:

最坏情况:从头找到尾 O(N)

最好情况:第一个就找到了 O(1)

平均情况:在中间位置找到的 O(n/2)

image-20220421121104894

注意:在实际中一般情况关注的是算法的最坏运行情况

2.4 时间复杂度的练习

练习1:

	// 计算func2的时间复杂度?
    void func2(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);
    }

image-20220421121618806

练习2:

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

image-20220421121710162

练习3:

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

image-20220421121827890

练习4:

	// 计算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;
            }
        }
    }

要求:分析出最坏情况以及最好情况

image-20220421122113009

在这里插入图片描述
上难度啦
在这里插入图片描述

练习5:

	// 计算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;
    }

image-20220421142046326

练习6:

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

小妙招:递归的时间复杂度=递归的次数*每次递归以后执行的次数

三目运算符:每次递归以后执行的次数为1

image-20220421142657965

练习7:

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

image-20220421143213021

在这里插入图片描述

至此为止,我们已经见过了O(N),O(N^2),O(1),O(N*LogN)这几个常见的时间复杂度,那么他们谁快谁慢怎么判断?

教大家一个小妙招:

记住最快的O(1) 最慢的 O(N^2)

其他带2 4这两个数判断大小

那么他们的顺序由快到慢分别是:

image-20220421143755007

3、空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,空间复杂度不是程序占用了多少byte的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。

举几个栗子:

栗子1:

	// 计算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;
            }
        }
    }

image-20220421213207506

栗子2:

	// 计算fibonacci的空间复杂度?
    int[]bonacci(int n) {
        long[] fibArray = new long[n + 1];
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i <= n ; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
        }
        return fibArray;
    }

image-20220421213325005

栗子3:

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

实例3递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)

image-20220421213516366


到这里,咱们时间复杂度以及空间复杂度就讲完了~
感谢多多支持~
在这里插入图片描述


原文连接:https://blog.csdn.net/m0_53117341/article/details/124495058

相关推荐

坚持用C++刷牛客题(剑指offer专题)

简答一波 HashMap 常见八股面试题 —— 算法系列(2)

LeetCode周赛302,这也太卷了,20分钟ak也只有300名……

「Java数据结构」手撕数组队列及环形数组队列。

挑战全网最详细讲解 平衡二叉树 AVL,手把手带你手撕 AVL !!!

【数据结构】插入排序(直接插入排序 && 希尔排序)

【C语言进阶】自定义类型——结构体

洛谷每日三题之第六天

【27. 表达式求值(中缀表达式)】

数据结构之【堆】(Heap)

经典TopK问题、优先级队列 与 堆的纠葛一文为你解惑——数据结构

2022-7-15 java 数据结构入门

树状数组

Java | 平铺列表(List)互转树形(Tree)结构

算法秒懂之背包问题(DP)-附牛客网真题实战

【二叉树】之力扣牛客必刷题

求数据流中的中位数问题

字典树及其实现

【数据结构】栈实现队列 & 队列实现栈

python查找与排序算法详解(示意图+代码、看完基础不成问题)