学了这么多年算法,你还不知道时间复杂度和空间复杂度如何计算吗?

点击上方蓝字即可关注我,如果觉得我的文章不错的话,建议将该公众号置顶/星标(点击作者蓝字然后点击右上角),有惊喜哦!

前言

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

时间复杂度

首先要说的是,时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的次数。

常见的时间复杂度

学了这么多年算法,你还不知道时间复杂度和空间复杂度如何计算吗?
常见的时间复杂度

计算方法

  1. 选取相对增长最高的项

  2. 最高项系数是都化为1

  3. 若是常数的话用O(1)表示

比如 f(n)=2*n^3+2n+100 的时间复杂度为: O(n)=n^3。

通常我们计算时间复杂度都是计算最坏情况

计算方法示例

(1)如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

    int x=1;
    while (x <10)
    {
        x++;
    }

该算法执行次数是10,是一个常数,用时间复杂度表示是O(1)。

(2)当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            ;
        }
    }

该算法for循环,最外层循环每执行一次,内层循环都要执行n次,执行次数是根据n所决定的,时间复杂度是O(n^2)。

(3)循环不仅与n有关,还与执行循环所满足的判断条件有关。

int i=0;
while (i < n && arr[i]!=1)
    {
        i++;
    }

在此循环中,如果arr[i]不等于1的话,时间复杂度是O(n)。如果arr[i]等于1的话,则循环不能执行,时间复杂度是0。

空间复杂度

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

计算方法

  1. 忽略常数,用O(1)表示

  2. 递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间

  3. 对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

计算方法示例

int a;
int b;
int c;
printf("%d %d %d n",a,b,c);

它的空间复杂度O(n)=O(1);

int fun(int n,)
{
int k=10;
if(n==k)
return n;
else
return fun(++n);
}

递归实现,调用fun函数,每次都创建1个变量k。调用n次,空间复杂度O(n*1)=O(n)。

以上内容参考:

  • https://blog.csdn.net/halotrriger/article/details/78994122


通过快排算法分析时间和空间复杂度计算

快排的基本思想

通过选择的参考值将待排序记录分割成独立的两部分,一部分全小于选取的参考值,另一部分全大于选取的参考值。对分割之后的部分再进行同样的操作直到无法再进行该操作位置(可以使用递归)。

一种简单快排的实现

下面是我写的一个简单的快排算法,我选择的参考值是数组的第一个元素

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] num = { 1348510221516 };
        QuickSort.quickSort(num, 0, num.length - 1);
        System.out.println(Arrays.toString(num));
    }

    public static void quickSort(int[] a, int start, int end) {
        // 该值定义了从哪个位置开始分割数组
        int ref;
        if (start < end) {
            // 调用partition方法对数组进行排序
            ref = partition(a, start, end);
            // 对分割之后的两个数组继续进行排序
            quickSort(a, start, ref - 1);
            quickSort(a, ref + 1, end);
        }
    }

    /**
     * 选定参考值对给定数组进行一趟快速排序
     * 
     * @param a
     *            数组
     * @param start
     *            (切分)每个数组的第一个的元素的位置
     * @param end
     *            (切分)每个数组的最后一个的元素位置
     * @return 下一次要切割数组的位置
     */

    public static int partition(int[] a, int start, int end) {
        // 取数组的第一个值作为参考值(关键数据)
        int refvalue = a[start];
        // 从数组的右边开始往左遍历,直到找到小于参考值的元素
        while (start < end) {
            while (end > start && a[end] >= refvalue) {
                end--;
            }
            // 将元素直接赋予给左边第一个元素,即pivotkey所在的位置
            a[start] = a[end];

            // 从序列的左边边开始往右遍历,直到找到大于基准值的元素
            while (end > start && a[start] <= refvalue) {
                start++;
            }
            a[end] = a[start];
            return end;
        }
        // 最后的start是基准值所在的位置
        a[start] = refvalue;
        return start;
    }

}

上述快排时间复杂度分析

  • 在最差情况下,划分由 n 个元素构成的数组需要进行 n 次比较和 n 次移动。因此划分所需时间为 O(n) 。最差情况下,每次主元会将数组划分为一个大的子数组和一个空数组。这个大的子数组的规模是在上次划分的子数组的规模减 1 。该算法需要 (n-1)+(n-2)+…+2+1= O(n^2) 时间。 T(n)=O(n^2) 。

  • 在最佳情况下,每次主元将数组划分为规模大致相等的两部分。设 T(n) 表示使用快速排序算法对包含 n 个元素的数组排序所需的时间,因此,和归并排序的分析相似,快速排序的 T(n)= O(nlogn)。

  • 在平均情况下, T(n)= O(nlogn)。

上述快排空间复杂度分析

首先就地快速排序使用的空间是O(1)的,也就是个常数级;而真正消耗空间的就是递归调用了,因为每次递归就要保持一些数据;

  • 最优情况:O(logn) ;每一次都平分数组的情况

  • 最差情况:O( n ) ;退化为冒泡排序的情况

  • 平均情况:O(logn)

另外,推荐给大家几篇类似的文章:

  • https://blog.csdn.net/zolalad/article/details/11848739

  • https://blog.csdn.net/yuzhihui_no1/article/details/44198701

笔主不是专门搞算法研究的,对于时间复杂度和空间复杂度就暂时研究到这里吧!

往期精彩回顾

最最最常见的Java面试题总结——第一周

最最最常见的Java面试题总结——第二周

Java 基础知识30问

这几道 Java 集合框架面试题在面试中几乎必问

如果不会这几道多线程基础题,请自觉面壁

可能是把 zookeeper 概念讲的最清楚的一篇文章

【面试必备】源码角度一步一步分析 ArrayList 扩容机制


温馨提示

如果你喜欢本文,请分享到朋友圈,想要获得更多信息,请点击下方二维码关注我。

学了这么多年算法,你还不知道时间复杂度和空间复杂度如何计算吗?


原文始发于微信公众号( Java面试通关手册 ):学了这么多年算法,你还不知道时间复杂度和空间复杂度如何计算吗?