算法复杂度分析

为什么要进行算法分析?

  • 预测算法所需的资源
    • 计算时间(CPU 消耗)
    • 内存空间(RAM 消耗)
    • 通信时间(带宽消耗)
  • 预测算法的运行时间
    • 在给定输入规模时,所执行的基本操作数量。
    • 或者称为算法复杂度(Algorithm Complexity)

如何衡量算法复杂度?

  • 内存(Memory)
  • 时间(Time)
  • 指令的数量(Number of Steps)
  • 特定操作的数量
    • 磁盘访问数量
    • 网络包数量
  • 渐进复杂度(Asymptotic Complexity)

算法的运行时间与什么相关?

  • 取决于输入的数据。(例如:如果数据已经是排好序的,时间消耗可能会减少。)
  • 取决于输入数据的规模。(例如:6 和 6 * 109)
  • 取决于运行时间的上限。(因为运行时间的上限是对使用者的承诺。)

算法分析的种类:

  • 最坏情况(Worst Case):任意输入规模的最大运行时间。(Usually)
  • 平均情况(Average Case):任意输入规模的期待运行时间。(Sometimes)
  • 最佳情况(Best Case):通常最佳情况不会出现。(Bogus)

例如,在一个长度为 n 的列表中顺序搜索指定的值,则

  • 最坏情况:n 次比较
  • 平均情况:n/2 次比较
  • 最佳情况:1 次比较

而实际中,我们一般仅考量算法在最坏情况下的运行情况,也就是对于规模为 n 的任何输入,算法的最长运行时间。这样做的理由是:

1、一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界(Upper Bound)。

2、对于某些算法,最坏情况出现的较为频繁。

3、大体上看,平均情况通常与最坏情况一样差。

算法分析要保持大局观(Big Idea),其基本思路:

1、忽略掉那些依赖于机器的常量。

2、关注运行时间的增长趋势。

比如:T(n) = 73n3 + 29n3 + 8888 的趋势就相当于 T(n) = Θ(n3)。

渐近记号(Asymptotic Notation)通常有 O、 Θ 和 Ω 记号法。Θ 记号渐进地给出了一个函数的上界和下界,当只有渐近上界时使用 O 记号,当只有渐近下界时使用 Ω 记号。尽管技术上 Θ 记号较为准确,但通常仍然使用 O 记号表示。

使用 O 记号法(Big O Notation)表示最坏运行情况的上界。例如,

  • 线性复杂度 O(n) 表示每个元素都要被处理一次。
  • 平方复杂度 O(n2) 表示每个元素都要被处理 n 次。

例如:

  • T(n) = O(n3) 等同于 T(n) ∈ O(n3)
  • T(n) = Θ(n3) 等同于 T(n) ∈ Θ(n3).

相当于:

  • T(n) 的渐近增长不快于 n3。
  • T(n) 的渐近增长与 n3 一样快。

注1:快速的数学回忆,logab = y 其实就是 ay = b。所以,log24 = 2,因为

22 = 4。同样 log28 = 3,因为 23 = 8。我们说,log2n 的增长速度要慢于 n,因为当 n = 8 时,log2n = 3。

注2:通常将以 10 为底的对数叫做常用对数。为了简便,N 的常用对数 log10 N 简写做 lg N,例如 log10 5 记做 lg 5。

注3:通常将以无理数 e 为底的对数叫做自然对数。为了方便,N 的自然对数 loge N 简写做 ln N,例如 loge 3 记做 ln 3。

注4:在算法导论中,采用记号 lg n = log2 n ,也就是以 2 为底的对数。改变一个对数的底只是把对数的值改变了一个常数倍,所以当不在意这些常数因子时,我们将经常采用 "lg n"记号,就像使用 O 记号一样。计算机工作者常常认为对数的底取 2 最自然,因为很多算法和数据结构都涉及到对问题进行二分。

而通常时间复杂度与运行时间有一些常见的比例关系:

计算代码块的渐进运行时间的方法有如下步骤:

1、确定决定算法运行时间的组成步骤。

2、找到执行该步骤的代码,标记为 1。

3、查看标记为 1 的代码的下一行代码。如果下一行代码是一个循环,则将标记 修改为 1 倍于循环的次数 1 * n。如果包含多个嵌套的循环,则将继续计算倍数,例如 1 * n * m。

4、找到标记到的最大的值,就是运行时间的最大值,即算法复杂度描述的上界。

示例代码(1):

decimal Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); }

阶乘(factorial),给定规模 n,算法基本步骤执行的数量为 n,所以算法复杂度为 O(n)。

示例代码(2):

int FindMaxElement(int[] array) { int max = array[0]; for (int i = 0; i < array.Length; i++) { if (array[i] > max) { max = array[i]; } } return max; }

这里,n 为数组 array 的大小,则最坏情况下需要比较 n 次以得到最大值,所以算法复杂度为 O(n)。

示例代码(3):

long FindInversions(int[] array) { long inversions = 0; for (int i = 0; i < array.Length; i++) for (int j = i + 1; j < array.Length; j++) if (array[i] > array[j]) inversions++; return inversions; }

这里,n 为数组 array 的大小,则基本步骤的执行数量约为 n*(n-1)/2,所以算法复杂度为 O(n2)。

示例代码(4):

long SumMN(int n, int m) { long sum = 0; for (int x = 0; x < n; x++) for (int y = 0; y < m; y++) sum += x * y; return sum; }

给定规模 n 和 m,则基本步骤的执行数量为 n*m,所以算法复杂度为 O(n2)。

示例代码(5):

decimal Sum3(int n) { decimal sum = 0; for (int a = 0; a < n; a++) for (int b = 0; b < n; b++) for (int c = 0; c < n; c++) sum += a * b * c; return sum; }

这里,给定规模 n,则基本步骤的执行数量约为 n*n*n ,所以算法复杂度为 O(n3)。

示例代码(6):

decimal Calculation(int n) { decimal result = 0; for (int i = 0; i < (1 << n); i++) result += i; return result; }

这里,给定规模 n,则基本步骤的执行数量为 2n,所以算法复杂度为 O(2n)。

示例代码(7):

斐波那契数列:

Fib(0) = 0 Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2) F() = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); }

这里,给定规模 n,计算 Fib(n) 所需的时间为计算 Fib(n-1) 的时间和计算 Fib(n-2) 的时间的和。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

fib(5)

/ \

fib(4) fib(3)

/ \ / \

fib(3) fib(2) fib(2) fib(1)

/ \ / \ / \

通过使用递归树的结构描述可知算法复杂度为 O(2n)。

示例代码(8):

int Fibonacci(int n) { if (n <= 1) return n; else { int[] f = new int[n + 1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[n]; } }

同样是斐波那契数列,我们使用数组 f 来存储计算结果,这样算法复杂度优化为 O(n)。

示例代码(9):

int Fibonacci(int n) { if (n <= 1) return n; else { int iter1 = 0; int iter2 = 1; int f = 0; for (int i = 2; i <= n; i++) { f = iter1 + iter2; iter1 = iter2; iter2 = f; } return f; } }

同样是斐波那契数列,由于实际只有前两个计算结果有用,我们可以使用中间变量来存储,这样就不用创建数组以节省空间。同样算法复杂度优化为 O(n)。

示例代码(10):

通过使用矩阵乘方的算法来优化斐波那契数列算法。

static int Fibonacci(int n) { if (n <= 1) return n; int[,] f = { { 1, 1 }, { 1, 0 } }; Power(f, n - 1); return f[0, 0]; } static void Power(int[,] f, int n) { if (n <= 1) return; int[,] m = { { 1, 1 }, { 1, 0 } }; Power(f, n / 2); Multiply(f, f); if (n % 2 != 0) Multiply(f, m); } static void Multiply(int[,] f, int[,] m) { int x = f[0, 0] * m[0, 0] + f[0, 1] * m[1, 0]; int y = f[0, 0] * m[0, 1] + f[0, 1] * m[1, 1]; int z = f[1, 0] * m[0, 0] + f[1, 1] * m[1, 0]; int w = f[1, 0] * m[0, 1] + f[1, 1] * m[1, 1]; f[0, 0] = x; f[0, 1] = y; f[1, 0] = z; f[1, 1] = w; }

优化之后算法复杂度为O(log2n)。

示例代码(11):

在 C# 中更简洁的代码如下。

static double Fibonacci(int n) { double sqrt5 = Math.Sqrt(5); double phi = (1 + sqrt5) / 2.0; double fn = (Math.Pow(phi, n) - Math.Pow(1 - phi, n)) / sqrt5; return fn; }

示例代码(12):

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的有序数据。算法适用于少量数据的排序,时间复杂度为 O(n2)。

private static void InsertionSortInPlace(int[] unsorted) { for (int i = 1; i < unsorted.Length; i++) { if (unsorted[i - 1] > unsorted[i]) { int key = unsorted[i]; int j = i; while (j > 0 && unsorted[j - 1] > key) { unsorted[j] = unsorted[j - 1]; j--; } unsorted[j] = key; } } }

原文发布于微信公众号 - 交互设计前端开发与后端程序设计(interaction_Designer)

原文发表时间:2016-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

Python Algorithms - C8 Dynamic Programming

Python算法设计篇(8) Chapter 8 Tangled Dependencies and Memoization

11130
来自专栏take time, save time

你所能用到的BMP格式介绍(一)

这些说明是我担任学校多媒体技术助教自己编写的实验说明,呕心沥血结合C++详细介绍BMP格式。  原理篇: 一、编码的意义。        让我们从一个简单的问题...

34270
来自专栏深度学习自然语言处理

【笔记】高效率但却没用过的一些numpy函数

最近在看源码的时候,碰到了一些大佬们常用,但自己暂时还没用过的numpy函数,特意来总结下。

7320
来自专栏一棹烟波

3DLut表实现log视频的后期调色原理

现在越来越多的视频或者图像拍摄设备支持log模式,比如大疆无人机的D-Log模式等等,log模式的起源和发展就不多做介绍,其在普通显示器上显示画面通常看起来是平...

37020
来自专栏数据小魔方

左手用R右手Python系列——数据塑型与长宽转换

今天这篇是R语言 with Python系列的第三篇,主要跟大家分享数据处理过程中的数据塑型与长宽转换。 其实这个系列算是我对于之前学习的R语言系列的一个总结,...

38060
来自专栏陈树义

图灵机 快速入门教程

图灵机是图灵机理论中提出的理想模型,其可以实现任意复杂的计算。 ? 什么是图灵机 英国数学家艾伦·图灵在1936年提出了「图灵机」的理论。「图灵机」设想有一条...

45940
来自专栏WindCoder

最大流量和线性分配问题

这里有一个问题:你的业务分配给承包商来履行合同。您可以浏览您的名单,并决定哪些承包商可以参与一个月的合同,你可以查看你的合同,看看哪些合同是一个月的任务。鉴于你...

27020
来自专栏机器之心

深度 | 从概念到实践,我们该如何构建自动微分库

30580
来自专栏Python小屋

三种Fibonacci数列第n项计算方法及其优劣分析

感谢国防科技大学刘万伟老师和中国传媒大学胡凤国两位老师提供的思路,文章作者不能超过8个字符,我的名字就写个姓吧,名字不写了^_^。另外,除了本文讨论的三种方法,...

34670
来自专栏章鱼的慢慢技术路

牛客网平台常州大学新生寒假训练会试

22930

扫码关注云+社区

领取腾讯云代金券