算法分析
2016年5月9日
1:15
主要包括 对时空复杂度的分析 ，还有算法的实际运行性能及算法可视化。
步骤：
1.量化算法的实际运行性能
| 选择衡量算法实际性能的量化指标是他的实际运行时间。这与算法要解决的问题规模有关。 /* 大O符号是一种算法复杂度的相对表示方式。 复杂度（complexity，就是操作的数量）。 我们称这为O(n)或者线性复杂度（linear complexity）。
我们只关心复杂度最重要的部分，，对于占操作总量很小比例的可以忽略，当我们做6位数乘法时，如果其中一个是4位数另一个是6位数，那么我们只需做24次乘法操作。然而，对于那个’n’，我们仍然计算最坏情况，即乘数都是6位数的情况。因此，大O符号是关于一个算法的最坏情况的。
例子：O(n^2) ---平方复杂度 O(log n)---对数复杂度 ：可以是任意底数，无关紧要 O(1)---常数复杂度
电话簿搜索---二分搜索 对于算法，大O符号能够被用于决定3种情况：
旅行商问题的大O符号表示是O(n!)，即阶乘(factorial)或组合复杂度(combinatorial complexity)。 任何复杂度为O(na)的算法被称为有多项式复杂度(polynomial complexity)，或可以在多项式时间(polynomial time)内解决。 */
算法的运行时间究竟取决于什么,然而在实际的分析中，我们应该做的是集中注意力于最耗时的部分 ，对那些耗时大但只执行常数次的操作我们可以忽略
我们知道分析算法的时间复杂度只需要两步（比把大象放进冰箱还少一步：) ）：
例题： 1. 【腾讯】下面算法的时间复杂度是____ int foo(int n) { if (n <= 1) { return 1； } return n * foo(n - 1); } 看到这道题要我们分析算法时间复杂度后，我们要做的第一步便是确定关键操作，这里的关键操作显然是if语句，那么我们只需要判断if语句执行的次数即可。首先我们看到这是一个递归过程：foo会不断的调用自身，直到foo的实参小于等于1，foo就会返回1，之后便不会再执行if语句了。由此我们可以知道，if语句调用的次数为n次，所以时间复杂度为O(n)。 2. 【京东】以下函数的时间复杂度为____ void recursive(int n, int m, int o) { if (n <= 0) { printf("%d, %d\n", m, o); } else { recursive(n - 1, m + 1, o); recursive(n - 1, m, o + 1); } } 这道题明显要比上道题难一些，那么让我们来按部就班的解决它。首先，它的关键操作时if语句，因此我们只需判断出if语句的执行次数即可。以上函数会在n > 0的时候不断递归调用自身，我们要做的是判断在到达递归的base case（即n <= 0）前，共执行了多少次if语句。我们假设if语句的执行次数为T(n, m, o)，那么我们可以进一步得到：T(n, m, o) = T(n-1, m+1, o) + T(n-1, m, o+1) （当n > 0时）。我们可以看到base case与参数m, o无关，因此我们可以把以上表达式进一步简化为T(n) = 2T(n-1)，由此我们可得T(n) = 2T(n-1) = (2^2) * T(n-2)......所以我们可以得到以上算法的时间复杂度为O(2^n)。 3. 【京东】如下程序的时间复杂度为____（其中m > 1，e > 0） x = m; y = 1; while (x - y > e) { x = (x + y) / 2; y = m / x; } print(x); 以上算法的关键操作即while语句中的两条赋值语句，我们只需要计算这两条语句的执行次数即可。我们可以看到，当x - y > e时，while语句体内的语句就会执行，x = (x + y) / 2使得x不断变小（当y<<x时，执行一次这个语句会使x变为约原来的一半），假定y的值固定在1，那么循环体的执行次数即为~logm，而实际情况是y在每次循环体最后都会被赋值为m / x，这个值总是比y在上一轮循环中的值大，这样一来x-y的值就会更小，所以以上算法的时间复杂度为O(logm)。 4. 【搜狗】假设某算法的计算时间可用递推关系式T(n) = 2T(n/2) + n，T(1) = 1表示，则该算法的时间复杂度为____ 根据题目给的递推关系式，我们可以进一步得到：T(n) = 2(2T(n/4) + n/2) + n = ... 将递推式进一步展开，我们可以得到该算法的时间复杂度为O(nlogn) |
|