算法分析

发表于 | 分类于 |

算法分析

算法的时间复杂度分析

  • 事后分析估算方法：这种统计方法主要是通过设计好的测试程序和测试数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低，但这种方法有很大的缺陷：必须依据算法实现编制好的测试程序，通常需要花费大量的时间和精力，测试完了如果发现测试的是非常糟糕的算法，那么之前所做的事情就全部白费了，并且不同的测试环境(硬件设备)的差别导致测试的结果差异也很大。

  • 事前分析估算方法：在计算机程序编写前，根据统计方法对算法进行估算，经过总结，一个高级语言编写的程序在计算机上运行所消耗的时间取决于下列因素：

    • 算法采用的策略与方案；
    • 编译产生的代码质量；
    • 问题的输入规模(输入量的多少)
    • 机器执行指令的速度

    由此可见，抛开与计算机硬件、软件有关因素，一个程序运行的时间依赖于算法的好坏与问题的输入规模。如果算法固定，那么算法的执行时间就只和问题的输入规模有关系了。

    我们研究算法复杂度，侧重的是当输入规模不断增大时，算法的增长量的一个抽象，而不是精确地定位需要执行多少次，因为如果是这样的话，我们又得考虑回编译器优化等问题，容易主次颠倒。我们分析一个算法的运行时间，最重要的就是把核心操作的次数和输入规模关联起来。

函数渐进增长

概念 ：给定两个函数$f(n)和g(n)$，如果存在一个整数N，使得对于所有的$n > N$，$f(n)$总是比$g(n)$大，那么我们说$f(n)$的增长渐进快于$g(n)$。

在比较随着输入规模的增长量时，可以有以下规则：

  • 算法函数中的常数可以忽略；
  • 算法函数中最高次幂的常数因子可以忽略；
  • 算法函数中最高次幂越小，算法效率越高。

算法时间复杂度

大O记法

定义：在进行算法分析时，语句总的执行次数$T(n)$是关于问题规模$n$的函数，进而分析$T(n)$随着$n$的变化情况并确定$T(n)$的量级。算法的时间复杂度，就是算法的时间度量，记作：$T(n)=O(f(n))$。它表示随着问题规模$n$的增长，算法执行时间的增长率和$f(n)$的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度，其中$f(n)$是问题规模$n$的某个函数。

在这里，我们需要明确一个事情：执行次数=执行时间

用大写$O()$来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模$n$的增长，$T(n)$增长最慢的算法为最优算法。

基于对函数渐进增长的分析，推导大$O$阶的表示方法有以下几个规则可以使用：

  • 用常数1取代运行时间中的所有加法常数；
  • 在修改后的运行次数中，只保留高阶项；
  • 如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数。

常见的大O阶

  • 线性阶：一般含有非嵌套循环及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长。
  • 平方阶：一般嵌套循环属于这种时间复杂度。
  • 立方阶：一般三层嵌套循环属于这种时间复杂度。
  • 对数阶：
  • 常数阶：一般不涉及循环操作的都是常数阶。

函数调用的时间复杂度分析

最坏情况

1
2
3
4
5
6
7
8
9
public int search(int num){
    int[] arr = {11,10,9,8,6,7,22,33,0};
    for(int i = 0; i < arr.length; i++){
        if(num == arr[i]){
            return i;
        }
    }
    return -1;
}
  • 最好情况：查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)
  • 最坏的情况：查找最后一个数字，才是期望的数字，那么算法的时间复杂度为O(n)
  • 平均情况：任何数字查找的平均成本是O(n/2)

算法的空间复杂度分析

JAVA中常见内存占用

  • 1.基本数据类型内存占用：

    • byte：1字节
    • short：2字节
    • int：4字节
    • long：8字节
    • float：4字节
    • double：8字节
    • boolean：4字节
    • char：2字节

  • 2.计算机访问内存的方式都是一次一个字节

  • 3.一个引用需要8个字节表示：

    例如：Date date = new Date()，则date变量需要占用8个字节来表示

  • 4.创建一个对象，比如new Date()，除了Date对象内部存储的数据占用的内存，该对象本身也有内存开销，每个对象的自身开销是16个字节，用来保存对象的头信息。

  • 5.一般内存的使用，如果不够8个字节，都会被自动填充为8字节

    例如：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public class A{
        public int a = 1;
    }
    /**
    通过new A()创建一个对象的内存占用如下：
    1.整型成员变量a占用4个字节；
    2.对象本身占用16个字节；
    那么创建该对象总共需要20个字节，但由于不是以8为单位，会自动填充为24个字节。
    */

  • 6.Java数组被限定为对象，它们一般会记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销，4个字节用于保存长度以及4个填充字节)再加上保存值所需的内存。

算法的空间复杂度

算法的空间复杂度计算公式记作：$S(n) = O(f(n))$，其中$n$为输入规模，$f(n)$为语句关于$n$所占存储空间的函数。

例：对指定的数组元素进行反转，并返回反转的内容。

1
2
3
4
5
6
7
8
9
10
public static int[] reverse1(int[] arr){
    int n = arr.length;//申请4个字节
    int temp;//申请4个字节
    for(int start = 0, end = n - 1; start <= end; start++, end--){
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
    return arr;
}
1
2
3
4
5
6
7
8
public static int[] reverse2(int[] arr){
    int n = arr.length;//申请4个字节
    int[] temp = new int[n];//申请n*4个字节+数组自身的头信息24个字节
    for(int i = n - 1; i >= 0; i--){
        temp[n-1-i] = arr[i];
    }
    return temp;
}

由于Java中有内存垃圾回收机制，并且$jvm$对程序的内存占用也有优化，无法精确的评估一个Java程序的内存占用情况，但是了解Java的基本内存占用，使得可以对Java程序内存占用情况进行估算。

由于现在计算机设备内存一般比较大，基本上个人计算机都是4G起步，大的可以达到32G，所以内存占用一般情况下并不是我们算法的瓶颈，普通情况下直接说复杂度，默认为算法的时间复杂度。

但是，如果你做的是嵌入式开发，尤其是传感器设备上的内置程序，由于这些设备的内存很小，一般为几$kb$，这个时候对算法的空间复杂度就有要求了，如果做Java开发，基本上是基于服务器开发，一般不存在这样的问题。

Donate comment here