8.1. 计算程序运行时间本模块讨论了对几种简单代码片段的分析。我们将使用算法分析简化规则：
如果 \(f(n)\) 在 \(O(g(n))\) 中且 \(g(n)\) 在 \(O(h(n))\) 中，那么 \(f(n)\) 在 \(O(h(n))\) 中。
如果对于任何常数 \(k > 0\) ， \(f(n)\) 在 \(O(k g(n))\) 中，则 \(f(n)\) 在 \(O(g(n))\) 中。
如果 \(f_1(n)\) 在 \(O(g_1(n))\) 中且 \(f_2(n)\) 在 \(O(g_2(n))\) 中，那么 \(f_1(n) + f_2(n)\) 在 \(O(\max(g_1(n), g_2(n)))\) 中。
如果 \(f_1(n)\) 在 \(O(g_1(n))\) 中且 \(f_2(n)\) 在 \(O(g_2(n))\) 中，那么 \(f_1(n) f_2(n)\) 在 \(O(g_1(n) g_2(n))\) 中。
Example 5.8.2
考虑一个简单的 for
sum = 0 ;
for ( i = 1 ; i <= n ; i ++ ) {
sum += n ;
}
sum = 0 ;
for ( i = 1 ; i <= n ; i ++ )
sum += n ;
第一行是 \(\Theta(1)\) 。 for \(n\) 次。第三行耗时为常数，因此，根据简化规则 (4)，执行构成 for \(\Theta(n)\) 。根据规则 (3)，整个代码片段的成本也为 \(\Theta(n)\) 。
Example 5.8.3
我们现在分析一段包含多个 for
sum = 0 ;
for ( j = 1 ; j <= n ; j ++ ) { // First for loop
for ( i = 1 ; i <= j ; i ++ ) { // is a double loop
sum ++ ;
}
}
for ( k = 0 ; k < n ; k ++ ) { // Second for loop
A [ k ] = k ;
}
sum = 0 ;
for ( j = 1 ; j <= n ; j ++ ) // First for loop
for ( i = 1 ; i <= j ; i ++ ) // is a double loop
sum ++ ;
for ( k = 0 ; k < n ; k ++ ) // Second for loop
A [ k ] = k ;
这段代码片段包含三个独立的语句：第一个赋值语句和两个 for \(c_1\) 。第二个 for 5.8.2 中的循环完全相同，耗时 \(c_2 n = \Theta(n)\) 。
首先， for sum++ \(c_3\) 。因为内部 for \(j\) 次，通过简化规则 (4)，其成本为 \(c_3j\) 。外部 for \(n\) 次，但每次内部循环的成本都不同，因为它每次的成本为 \(c_3j\) ，而 \(j\) 每次都在变化。你应该看到，对于外部循环的第一次执行， \(j\) 为 1。对于外部循环的第二次执行， \(j\) 为 2。每次通过外部循环， \(j\) 就增加 1，直到最后一次通过循环时， \(j = n\) 。因此，该循环的总成本为 \(c_3\) 乘以从 1 到 \(n\) 的整数之和。我们已知
\[\sum_{i = 1}^{n} i = \frac{n (n+1)}{2},\]
which is \(\Theta(n^2)\) .
By simplifying rule (3), \(\Theta(c_1 + c_2 n + c_3 n^2)\) is
simply \(\Theta(n^2)\) .
Example 5.8.4
比较以下两个代码片段的渐近分析。
sum1 = 0 ;
for ( i = 1 ; i <= n ; i ++ ) { // First double loop
for ( j = 1 ; j <= n ; j ++ ) { // do n times
sum1 ++ ;
}
}
sum2 = 0 ;
for ( i = 1 ; i <= n ; i ++ ) { // Second double loop
for ( j = 1 ; j <= i ; j ++ ) { // do i times
sum2 ++ ;
}
}
sum1 = 0 ;
for ( i = 1 ; i <= n ; i ++ ) // First double loop
for ( j = 1 ; j <= n ; j ++ ) // do n times
sum1 ++ ;
sum2 = 0 ;
for ( i = 1 ; i <= n ; i ++ ) // Second double loop
for ( j = 1 ; j <= i ; j ++ ) // do i times
sum2 ++ ;
在第一个双重循环中，内部 for \(n\) 次。因为外部循环执行 \(n\) 次，所以可以明显看出语句 sum1++ \(n^2\) 次。第二个循环类似于前一个例子中分析的循环，其成本为 \(\sum_{j = 1}^{n} j\) 。这大约是 \({1 \over 2} n^2\) 。因此，两个双重循环的成本都是 \(\Theta(n^2)\) ，尽管第二个循环大约需要第一个循环一半的时间。
Example 5.8.5
并非所有双重嵌套 for \(\Theta(n^2)\) 。以下成对嵌套循环说明了这一事实。
sum1 = 0 ;
for ( k = 1 ; k <= n ; k *= 2 ) { // Do log n times
for ( j = 1 ; j <= n ; j ++ ) { // Do n times
sum1 ++ ;
}
}
sum2 = 0 ;
for ( k = 1 ; k <= n ; k *= 2 ) { // Do log n times
for ( j = 1 ; j <= k ; j ++ ) { // Do k times
sum2 ++ ;
}
}
sum1 = 0 ;
for ( k = 1 ; k <= n ; k *= 2 ) // Do log n times
for ( j = 1 ; j <= n ; j ++ ) // Do n times
sum1 ++ ;
sum2 = 0 ;
for ( k = 1 ; k <= n ; k *= 2 ) // Do log n times
for ( j = 1 ; j <= k ; j ++ ) // Do k times
sum2 ++ ;
在分析这两个代码片段时，我们将假设 \(n\) 是 2 的幂。第一个代码片段的外层 for \(\log n+1\) 次，因为在每次迭代中 \(k\) 都被乘以 2，直到达到 \(n\) 。由于内层循环总是执行 \(n\) 次，因此第一个代码片段的总成本可以表示为
\[\sum_{i=0}^{\log n} n = n \log n.\]
So the cost of this first double loop is \(\Theta(n \log n)\) .
Note that a variable substitution takes place here to create the
summation, with \(k = 2^i\) .
In the second code fragment, the outer loop is also executed
\(\log n+1\) times.
The inner loop has cost \(k\) , which doubles each time.
The summation can be expressed as
\[\sum_{i=0}^{\log n} 2^i = \Theta(n)\]
where \(n\) is assumed to be a power of two and again
\(k = 2^i\) .
那其他的控制语句呢？ While for if then else \(n\) 的大小不影响执行其中一个子句的概率（这通常是，但不一定是真的）。对于 switch
存在罕见的情况，执行 if switch \(n\) 的输入， if then \(1/n\) 的概率被执行。一个例子是 if \(n\) 个值中执行 then if 摊销分析
确定递归子程序的执行时间可能很困难。递归子程序的运行时间通常最好用递推关系来表示。例如，递归阶乘函数会以比输入值小一的值调用自身。然后，将递归调用的结果乘以输入值，这需要常数时间。因此，如果我们希望以乘法操作的数量来衡量成本，那么阶乘函数的成本比递归调用在较小输入上所做的乘法数量多一次。因为基本情况不做乘法，其成本为零。因此，该函数的运行时间可以表示为
\[T(n) = T(n-1) + 1 \ \mbox{for}\ n>1;\ \ T(1) = 0.\]
该递推关系的封闭形式解是 \(\Theta(n)\) 。
8.1.1. 案例研究：两种查找算法本节算法分析的最后一个例子将比较两种在数组中执行查找的算法。之前，我们确定在搜索值 \(K\) 等可能出现在任何位置的数组上执行顺序查找的运行时间是 \(\Theta(n)\) ，在平均情况和最坏情况下都是如此。我们希望将此运行时间与在值按从低到高顺序存储的数组上执行 二分查找
8.1.3. 分析二分查找函数 binarySearch \(K\) 的（单个）出现位置并返回其索引。如果 \(K\) 不在数组中，则返回一个特殊值。此算法可修改以实施变体，例如当允许多个出现时返回 \(K\) 在数组中首次出现的索引，或在 \(K\) 不在数组时返回小于 \(K\) 的最大值的索引。
将顺序查找与二分查找相比，我们看到，随着 \(n\) 的增长，平均情况和最坏情况下的 \(\Theta(n)\) 顺序查找的运行时间迅速变得远大于 \(\Theta(\log n)\) 二分查找的运行时间。孤立来看，二分查找似乎比顺序查找高效得多。尽管二分查找的常数因子大于顺序查找，因为二分查找中计算下一个搜索位置比顺序查找中仅仅递增当前位置更昂贵。
然而，请注意顺序查找的运行时间无论数组值是否按顺序存储大致相同。
