抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

时间复杂度和空间复杂度

覃浩

发布于：2021年5月20日
算法基础

字数：1.7k字

时长：7分钟
0  
次浏览

算法效率的度量方式

算法时间复杂度

推导大O阶方法

线性阶

平方阶

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

时间复杂度和空间复杂度

算法效率的度量方式

事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

事前分析估算方法：在计算机程序编写前，依据统计方法对算法进行估算。

经过总结，我们发现一个高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

  1. 算法采用的策略，方案
  2. 编译产生的代码质量
  3. 问题的输入规模
  4. 机器执行指令的速度

由此可见，抛开这些与计算机硬件，软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。（所谓的问题输入规模是指输入量的多少）

不同算法运行时间比较

第一种算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package 算法与数据结构;


public class Test1 {
    public static void main(String[] args) {
        int sum = 0;
        long begin_time = System.currentTimeMillis();
        for (int i = 1; i <= 100000000; i++) {
            sum += i;
        }
        long end_time = System.currentTimeMillis();
        System.out.println("sum = " + sum);
        System.out.println("运行时间：" + (end_time-begin_time));
    }
}

运行结果：

20210522091454

第二种算法：

1
2
3
4
5
6
7
8
9
10
11
12
package 算法与数据结构;

public class Test2 {
    public static void main(String[] args) {
        int sum;
        long begin = System.currentTimeMillis();
        sum = (1 + 1000000000) * 100000000 / 2 ;
        long end = System.currentTimeMillis();
        System.out.println("sum = " + sum);
        System.out.println("运行时间：" + (end - begin));
    }
}

运行结果：

20210522091531

第一种算法执行了1 + (n + 1) + n = 2n + 2次。

第二种算法，是1 + 1 = 2次

如果我们把循环看作一个整体，忽略头尾判断的开销，那么这两个算法其实就是n和1的差距。

我们研究算法的复杂度，侧重的是研究算法随着输入规模扩大增长量的一个抽象，而不是精确地定位需要执行多少次，因为如果这样的话，我们就又得考虑回编译器优化等问题。

函数的渐进增长

函数的渐进增长：给定两个函数f(n)和g(n)，如果存在一个整数 N ，使得对于所有的n > N，f(n) 总是比 g(n) 大，那么，我们说 f(n) 的增长渐进快于 g(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) 增长最慢的算法为最优算法。

推导大O阶方法

如何分析一个算法的时间复杂度呢？即如何推导大O阶呢？

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

线性阶

一般含有非嵌套循环涉及线性阶，线性阶就是随着问题的规模n的扩大，对应计算次数呈直线增长。

1
2
3
4
5
6
7
8
9
10
11
12
package 算法与数据结构;

public class Test3 {
    public static void main(String[] args) {
        int sum = 0;
        for(int i = 1;i <= 100;i ++)
        {
            sum += i;
        }
        System.out.println("sum  = " + sum);
    }
}

上面这段代码，他的循环的时间复杂度为O(n)，因为循环体中的代码需要执行n次。

平方阶

1
2
3
4
5
6
7
8
9
10
11
12
13
package 算法与数据结构;

public class Demo4 {
    public static void main(String[] args) {
        for(int i = 0;i < 100;i ++)
        {
            for(int j = 0;j < 100;j ++)
            {
                System.out.println("I love tttttt!");
            }
        }
    }
}

n等于100， 也就是说外层循环每执行一次，内层循环就执行100次，那总共程序想要从这两个循环出来，需要执行100*100次，也就是n的平方。所以这段代码的时间复杂度为O(n^2)。

循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
package 算法与数据结构;

public class Demo5 {
    public static void main(String[] args) {
        for(int i = 0;i < 100;i ++)
        {
            for(int j = i;j < 100;j ++)
            {
                System.out.println("I love tttttt!");
            }
        }
    }
}

由于当 i = 0 时，内循环执行了 n 次，当 i = 1时，内循环则执行 n - 1 次，当 i = n - 1时，内循环执行1次，所以总的执行次数应该是：
$$
-n + (n-1)+(n-2)+…+1 = \frac{n(n + 1)}{2}
$$
即：
$$
\frac{n(n+1)}{2}=\frac{n^2}{2}+\frac{n}{2}
$$
用推导大O的攻略，第一条忽略，因为没有常数相加。第二条只保留最高项，所以n/2这项去掉。第三条，去除与最高项相乘的常数，最终得O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
package 算法与数据结构;

public class Demo6 {
    public static void main(String[] args) {
        int i = 1;
        int n = 100;
        while(i < n)
        {
            i *= 2;
        }
    }
}

由2^n = n得到：
$$
x = log_2n
$$
所以这个循环的时间复杂度为O(logn)。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package 算法与数据结构;

public class Demo7 {

    static void function(int n){
        System.out.println(n);
    }

    public static void main(String[] args) {
        for(int i = 1;i <= 520;i ++)
        {
            function(i);
        }
    }
}

function函数的时间复杂度是O(1)，所以整体的时间复杂度就是循环的次数O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package 算法与数据结构;

public class Demo8 {
    public static void function(int count){
        for(int i = count;i <= 520;i ++)
        {
            System.out.println(i);
        }
    }

    public static void main(String[] args) {
        for(int i = 1;i <= 520;i ++)
        {
            function(i);
        }
    }
}

function内部的循环次数随count的增加（接近n）而减少，所以根据推导大O阶方法可得出算法的时间复杂度为O(n^2)。

更新于：2021年12月30日

评论




2019-2022 覃浩的博客 丨 鄂ICP备2021017381号-1 丨 正在载入... 丨

PoweredHexo
HostedGitHub & Coding
DNSDNSPod
CDN腾讯云CDN
PictureBed腾讯云CDN
ThemeVolantis