算法——算法分析

踏踏实实学算法，从今天开始，从现在开始。

本篇博文根据数据结构与问题求解Java语言描述（第3版）（Data Structure and Problem Solving Using Java Third Edition）整理而成。百度百科 豆瓣评分

算法：算法是一个明确指定的指定集合，计算机将按照这个指令集解决某个问题。 算法分析：对某个问题给定一个算法且证明这个算法是正确的，下一步就是要确定该算法所需要的资源（时间，空间等）量。

1.1 算法分析的几个要点

任何算法运行所需的时间几乎总是取决于它必须处理的输入数据量。数据越多意味着程序运行要花的时间越长。算法分析常见函数包括N^2, NlogN, N(线性)，logN，C。其中线性算法效率最高，NlogN更接近N。当输入数据量n足够大时，考察函数的增长率是最重要的，并且只考虑主项即最大的项。

按增长率升序排列的函数

函数名称c常数logN对数(logN)^2对数的平方N线性NlogNNlogNN^2平方N^3立方2^N指数

1.2 算法运行时间的实例

问题描述：求连续子序列最大和的问题：给定整数序列a1, a2, … , aN（可为负值），寻找一个连续子序列：该序列的和在所有连续子序列中最大。如果所有的整数是负的，那么连续子序列的最大和为0。 连续子序列：在一个包含N个元素的序列中，连续X个元素组成的序列，其中0<=X<=N。 连续子序列的和：当X=0时，该序列的和为0；当X>0是，子序列中各元素相加求和。 引申：大部分算法总是要考虑空的问题。

1.2.1 简单的O(N^3)算法

思想：穷尽查找，暴力破解。

public static int maxSumWithN3(int[] array) { int maxSum = 0; int length = array.length; for (int i = 0; i < length; i++) { for (int j = i; j < length; j++) { int thisSum= 0; for (int k = i; k <= j; k++) { thisSum += array[k]; } if (thisSum > maxSum) { maxSum = thisSum; } } } return maxSum; }

1.2.2 改进的O(N^2)算法

思想：从上一个算法中删除一层循环，降低运行时间：假设已经计算出子序列i, … , j-1的和，只要再做一次加法，就可以计算出i, … , j的和，利用这一观察结果进行改进，得到如下算法。

public static int maxSumWithN2(int[] array) { int maxSum = 0; int length = array.length; for (int i = 0; i < length; i++) { int thisSum = 0; for (int j = i; j < length; j++) { thisSum += array[j]; if (thisSum > maxSum) { maxSum = thisSum; } } } return maxSum; }

1.2.3 线性算法

思想：再去掉一层循环，包含子序列（和为负数）的序列不可能是最大连续子序列，当检测出一个和为负的子序列时，不但可以从内层循环中跳出来，而且还可以让i直接增加到j+1。

public static int maxSumWithN(int[] array) { int maxSum = 0; int thisSum = 0; int length = array.length; for (int i = 0, j = 0; j < length; j++) { thisSum += array[j]; if (thisSum > maxSum) { maxSum = thisSum; } else if (thisSum < 0) { i = j + 1; thisSum = 0; } } return maxSum; }

1.3 算法分析的检查

一旦完成了算法分析，我们需要判断它是否正确以及是否尽可能地好。 1. 一种方法是编一个程序，然后看看观测到的运行时间和分析中预测出的运行时间是否匹配。当N增加10倍时，线性程序的运行时间增加10倍，平方程序增加100倍，以O(NlogN)时间运行的程序所用时间增加10倍多一点。 2. 另一个经常用于证明某些程序是O(F(N))的技巧是，在N的某个范围（通常是2的整倍数分隔：10000-20000-40000-80000等）内计算T(N)/F(N)的值，T(N)为输入数据个数为N时的程序运行时间，F(N)为N,NlogN,N^2等。如果F(N)是一个精确的答案，那么T(N)/F(N)将会收敛与一个正的常数。F(N)估计过高，这些值会收敛于0；F(N)估计过低，这些值会发散。

1.4 一般的大O原则

定义（大O）：如果存在正的常数c和N0，满足当N≥N0时有T(N)≤cF(N)，则T(N)是O(F(N))。定义（大 Ω ）：如果存在正的常数c和N0，满足当N≥N0时有T(N)≥cF(N)，则T(N)是 Ω (F(N))。大O表示法说明了T(N)的增长率小于或等于F(N)的增长率。（上限）大 Ω 表示法说明了T(N)的增长率大于或等于F(N)的增长率。（下限）一般算法分析方法包括最坏情况限度分析和平均情况限度分析。

1.5 对数logN

问题1：从X=1开始，在X至少和N一样大之前应该翻倍多少次？ 问题2：从X=N开始，如果N重复地减半，要使N小于等于1需要减半多少次？ 答案1： ⌈logN⌉ 次（1*2^K >= N） 答案2： ⌈logN⌉ 次（结果向上取舍）或 ⌊logN⌋ 次（结果向下取舍）

logN理解为 log2N ，翻倍，减半。底数对于大O表示法无关紧要： logBN=log2N/log2B 。所以 logBN=O(logN) 在平方算法O(N^2)与线性算法O(N)中，O(NlogN)算法的性能更接近后者。

1.6 大O分析的局限性

最坏情况限度分析通常比对应的平均情况限度分析容易得到，我们使用最坏情况下的分析是因为它比较方便，而且在大多数情况很有意义。所以在分析的过程中，我们要考虑算法是否能应用平均情况，不能的话考虑最坏情况分析。