亲宝软件园·资讯

展开

前端数据结构---复杂度分析

风吹De麦浪 人气:0

为什么需要复杂度分析

  我们可以把代码跑一遍,然后通过一些工具来统计、监控就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢?这种分析方法能比我实实在在跑一遍得到的数据更准确吗?

  首先,肯定的说这种评估算法执行效率的方法是正确的。很多数据结构和算法书籍还给这种方法起了一个名字,叫事后统计法。但是这种统计方法存在一定的局限性。

1、测试结果依赖测试的环境以及数据规模的影响

  比如,我们拿同样一段代码,再不同的机器以及不同的数据规模可能会有不同的结果。

2、掌握复杂度分析,将能编写出性能更优的代码

所以我们需要一个不用具体的测试环境、测试数据来测试,就可以粗略地估计算法的执行效率的方法,这就是我们需要的时间、空间复杂度分析方法。

大 O 复杂度表示法

  算法的执行效率,简单的说就是代码执行的时间。但是怎么样在不运行代码的情况下,用“肉眼”得到一段代码的执行时间呢?这里有段非常简单的代码,求 1,2,3...n 的累加和。现在来估算一下这段代码的执行时间。

1 function countSum(n) {
2    let sum = 0;
3    console.log(n)
4    for (i = 0; i <= n; ++i) {
5      sum = sum + i;
6    }
7    return sum;
8  }

每行代码对应的 CPU 执行的个数、执行的时间都不一样,所以只是粗略估计,我们可以假设每行代码执行的时间都一样为 unit_time。在这个假设的基础之上,这段代码的总执行时间是多少呢?

第 2、3 行代码分别需要 1 个 unit_time 的执行时间,第 4、5 行都运行了 n 遍,所以需要 2n * unit_time 的执行时间,所以这段代码总的执行时间就是 (2n+2) * unit_time。

尽管我们不知道 unit_time 的具体值,但是通过代码执行时间的推导过程,我们可以得到一个非常重要的规律,那就是所有代码的执行时间 T(n) 与代码的执行次数 f(n) 成正比。

我们可以把这个规律总结成一个公式,这个公式就是数据结构书上说的大O表示法。

我来具体解释一下这个公式:

  • T(n) 表示代码执行的时间
  • n 表示数据规模的大小
  • f(n) 表示代码执行的次数总和

  因为这是一个公式,所以用 f(n) 来表示。公式中的 O,表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

  所以,上面例子中的 T(n) = O(2n+2),这就是大 O 时间复杂度表示法。大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

 

时间复杂度分析

分析大O一般的步骤如下:

  1. 用常数1代替运行中的所有的加法常数 n + 2 + 3 + 4 等于 n + 1
  2. 在修改后的运行次数函数中,只保留最高阶项 如 n^3 + n^2 等于 n^3
  3. 如果最高阶项存在且不为1,则去掉与这个项相乘的常数 如 3n^2 等于 n^2

通过上面三个步骤可以总结出几个方法

1. 只关注循环执行次数最多的一段代码

大 O 这种复杂度表示方法只是表示一种变化趋势。通过上面的公式我们会忽略掉公式中的常量、低阶、系数,只需要记录一个最大阶的量级。所以我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级,就是整段要分析代码的时间复杂度。

2.加法法则:总复杂度等于量级最大的那段代码的复杂度

如果是很长的一个代码段,可以把他们拆分计算时间复杂度,然后再加起来

 1 function countSum(n) {
 2    let sum_1 = 0;
 3    console.log('计算:sum_1')
 4    for (let p = 0; p < 100; ++p) {
 5      sum_1 = sum_1 + p;
 6    }
 7 
 8    let sum_2 = 0;
 9    console.log('计算:sum_2')
10    for (let q = 0; q < n; ++q) {
11      sum_2 = sum_2 + q;
12    }
13  
14    let sum_3 = 0;
15    console.log('计算:sum_3')
16    for (let i = 0; i <= n; ++i) {
17      j = 1; 
18      for (let j = 0; j <= n; ++j) {
19        sum_3 = sum_3 +  i * j;
20      }
21    }
22  
23    return sum_1 + sum_2 + sum_3;
24  }

这个代码分为三部分,分别是求 sum_1、sum_2、sum_3。我们可以分别分析每一部分的时间复杂度,然后把相加,再取一个量级最大的作为整段代码的复杂度。

第一段的时间复杂度是多少呢?这段代码循环执行了 100 次,所以是一个常量的执行时间,跟 n 的规模无关。强调一下,即便这段代码循环 10000 次、100000 次,只要是一个已知的数,跟 n 无关,照样也是常量级的执行时间。当 n 无限大的时候,就可以忽略。尽管对代码的执行时间会有很大影响,但是回到时间复杂度的概念来说,它表示的是一个算法执行效率与数据规模增长的变化趋势,所以不管常量的执行时间多大,我们都可以忽略掉。因为它本身对增长趋势并没有影响。

那第二段代码和第三段代码的时间复杂度应该很容易分析出来是 O(n) 和 O(n^2)。

综合这三段代码的时间复杂度,我们取其中最大的量级。所以,整段代码的时间复杂度就为 O(n^2)。也就是说:总的时间复杂度就等于量级最大的那段代码的时间复杂度。

3.乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

假设有一个嵌套的循环,我们把第一层循环叫T1,那么T1(n)=O(f(n)),第二层循环叫T2,那么T2(n)=O(g(n)),总共时间 T(n)=T1(n)*T2(n) = O(f(n))*O(g(n))= O(f(n) * g(n))

假设 T1(n) = O(n),T2(n) = O(n^2),则 T1(n) * T2(n) = O(n^3)。在具体的代码上,我们可以把乘法法则看成是嵌套循环

如上面计算sum_3的代码段 两个循环为O(n^2)。

常见时间复杂度实例分析

O(1)

O(1) 只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码。比如这段代码,即便有 3 行,它的时间复杂度也是 O(1),而不是 O(3)。

 

1 const i = 8; 
2 const j = 6; 
3 const sum = i + j;

只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度我们都记作 O(1)。或者说,一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。

O(logn)

对数阶时间复杂度非常常见,如

1 i=1;
2 while (i <= n) {
3   i = i * 2; 
4 }

根据说的复杂度分析方法,第三行代码是循环执行次数最多的。所以,我们只要能计算出这行代码被执行了多少次,就能知道整段代码的时间复杂度。从代码中可以看出,变量 i 的值从 1 开始取,每循环一次就乘以 2。当大于 n 时,循环结束。实际上变量 i 的取值就是一个等比数列。如果我把它一个一个列出来,就应该是这个样子的:

 所以,我们只要知道 x 值是多少,就知道这行代码执行的次数了。通过 2x=n 求解 x 这个问题我们想高中应该就学过了,我就不多说了。x=log2n,所以,这段代码的时间复杂度就是 O(log2n)。

O(n)

O(n)级别有个非常显著的特征就,它会存在一个循环,且循环的次数是和n相关

1 function countSum (n) {
2   let sum = 0
3   for (let i = 0; i < n; i++) {
4     sum += i
5   }
6 }

O(n^2) 

O(n^2)级别的有双重循环

function countSum (n) {
  let sum = 0
  for (let i = 0; i < n; i++) {
    sum += i
    for (let J = 0; J < n; i++) {
      // do some thing
   }
  }
}

不是所有的双重循环都是n^2

1 function countSum (n, m) {
2   let sum = 0
3   for (let i = 0; i < n; i++) {
4     sum += i
5     for (let J = 0; J < m; i++) {
6       // do some thing
7    }
8   }
9 }

这种是由两个数据规模n、m来决定的时间复杂度,所以是O(n * m),关键还是要分析嵌套的循环跟外面那层循环的关系。

时间复杂度耗费时间从小到大依次排列

  O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

常见排序算法对应的时间复杂度

排序方法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性复杂性
直接插入排序 O(n2)O(n2) O(n2)O(n2) O(n)O(n) O(1)O(1) 稳定 简单
希尔排序 O(nlog2n)O(nlog2n) O(n2)O(n2) O(n)O(n) O(1)O(1) 不稳定 较复杂
直接选择排序 O(n2)O(n2) O(n2)O(n2) O(n2)O(n2) O(1)O(1) 不稳定 简单
堆排序 O(nlog2n)O(nlog2n) O(nlog2n)O(nlog2n) O(nlog2n)O(nlog2n) O(1)O(1) 不稳定 较复杂
冒泡排序 O(n2)O(n2) O(n2)O(n2) O(n)O(n) O(1)O(1) 稳定 简单
快速排序 O(nlog2n)O(nlog2n) O(n2)O(n2) O(nlog2n)O(nlog2n) O(nlog2n)O(nlog2n) 不稳定 较复杂
归并排序 O(nlog2n)O(nlog2n) O(nlog2n)O(nlog2n) O(nlog2n)O(nlog2n) O(n)O(n) 稳定 较复杂
基数排序 O(d(n+r))O(d(n+r)) O(d(n+r))O(d(n+r)) O(d(n+r))O(d(n+r)) O(n+r)O(n+r) 稳定 较复杂

空间复杂度

 时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。同理,空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系,空间复杂度分析跟时间复杂度类似。

1 function run (n) {
2     let name = 'joel'
3     let step= 2
4     const arr = []
5 
6     for (let i = 0; i < n; i++) {
7       arr.push(i * step)
8    }
9 }

再第4行代码我们初始化一个数组,再第7行代码对这个数组进行push 操作,这个循环是依赖外部的n,所以这个空间复杂度为 O(n),我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )

 

加载全部内容

相关教程
猜你喜欢
用户评论