第 6 题 （1.5 分）
若某算法的计算时间表示为递推关系式：

T ( N ) = 2 T ( N / 2 ) + N l o g N T(N)=2T(N/2)+NlogN T(N)=2T(N/2)+NlogN
T ( N / 2 ) = 2 T ( N / 4 ) + ( N / 2 ) × l o g ( N / 2 ) = 2 T ( N / 4 ) + N / 2 × l o g N − N / 2 × l o g 2 T(N/2)=2T(N/4)+(N/2)×log(N/2)=2T(N/4)+N/2×logN−N/2×log2 T(N/2)=2T(N/4)+(N/2)×log(N/2)=2T(N/4)+N/2×logN−N/2×log2
…
将式②代入式①整理得： T ( N ) = 4 T ( N / 4 ) + N l o g N + N l o g N − N l o g 2 T(N)=4T(N/4)+NlogN+NlogN−Nlog2 T(N)=4T(N/4)+NlogN+NlogN−Nlog2，去常数项与低阶项为： T ( N ) = 4 T ( N / 4 ) + N l o g N + N l o g N T(N)=4T(N/4)+NlogN+NlogN T(N)=4T(N/4)+NlogN+NlogN
继续代入，一共有 l o g N logN logN项 N l o g N NlogN NlogN，故 O ( N ∗ l o g 2 N ) O(N∗log^2N) O(N∗log2N)

第 14 题 （1.5 分）
小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第 1个航班准点的概率是 0.9，第 2 个航班准点的概率为 0.8，第 3 个航班准点的概率为 0.9。如果存在第 i个 (i=1,2) 航班晚点，第 i+1个航班准点，则小明将赶不上第 i+1个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是___。

答案： 1 − 0.1 × 0.8 − 0.2 × 0.9 = 1 − 0.26 = 0.74 1−0.1×0.8−0.2×0.9=1−0.26=0.74 1−0.1×0.8−0.2×0.9=1−0.26=0.74

第 28 题
（最长路径）给定一个有向无环图，每条边长度为 1，求图中的最长路径长度。
输入：第一行是结点数 n（不超过 100）和边数 m，接下来 m 行，每行两个整数 a，b，表示从结点 a 到结点 b 有一条有向边。结点标号从 0 到 (n-1) 。
输出：最长路径长度。
提示：先进行拓扑排序，然后按照拓扑序计算。

#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100];        
int degree[100];            
int len[100];               
int queue[100];             
int main(){
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            graph[i][j] = 0;
    for (i = 0; i < n; i++)
        degree[i] = 0;
    for (i = 0; i < m; i++){
        cin >> a >> b;
        graph[a][b] = 1;
        ___(1)___ ;
    }
    tail = 0;
    for (i = 0; i < n; i++)
        if (___(2)___){
            queue[tail] = i;
            tail++;
        }
    head = 0;
    while (tail < n - 1){
        for (i = 0; i < n; i++)
            if (graph[queue[head]][i] == 1){
                ___(3)___ ;
                if (degree[i] == 0){
                    queue[tail] = i;
                    tail++;
                }
            }
        ___(4)___ ;
    }
    ans = 0;
    for (i = 0; i < n; i++){
        a = queue[i];
        len[a] = 1;
        for (j = 0; j < n; j++)
            if (graph[j][a] == 1 && len[j] + 1 > len[a])
                len[a] = len[j] + 1;
        if (___(5)___)
            ans = len[a];
    }
    cout << ans << endl;
    return(0);
}

①，统计b点入度，degree[b]++。
②，将入度为0的点入队，degree[i]==0
③，访问到相邻点i，将其入度减1，degree[i]–
④，队列顶点出队，head++
⑤，打擂台求最长路径长度，ans < len[a]