一.建立堆的复杂度证明

建立堆采用自下而上逐渐调整的方法，伪代码：

考虑最大的交换次数：
设元素个数为$n=2^h-1$n=2h−1,其中h是树高。一个第i层的元素最多向下走h-i步。所以最大交换总次数是$T=\sum_{i=0}^{h-1}2^i(h-(i+1))=h\sum_{i=0}^{h-1}2^i - \sum_{i=0}^{h-1}2^i(i +1)$T=i=0∑h−1​2i(h−(i+1))=hi=0∑h−1​2i−i=0∑h−1​2i(i+1)
前一项是个等比数列和，结果是$hn$hn；
后面那个把2看为自变量可以变成$f(x)=\sum_{i=0}^{h-1}x^{i+1}$f(x)=i=0∑h−1​xi+1在x=2时的导数。结果是$(h-1)2^h+1$(h−1)2h+1;
两者相减即可得$T=2^h-h-1=n-h$T=2h−h−1=n−h
每一步时间时常数级别，所以时间复杂度O(n)。

二. 定长路径的条数证明

用数学归纳法即可。
设A为邻接矩阵，$A^{n}[i,j]$An[i,j]表示ij之间长度为n的路径条数。要证明$A^{n+1}[i,j]$An+1[i,j]表示ij之间路径长为n+1的路径条数。
$A^{n+1}[i,j]=\sum_{k=1}^{k=n}A^n[i,k]*A[k,j]$An+1[i,j]=k=1∑k=n​An[i,k]∗A[k,j]
长度为n+1的可以按路径上第n个节点分类，有n类。第n个节点为k的条数根据乘法原理就是$A^n[i,k]*A[k,j]$An[i,k]∗A[k,j],在根据加法原理把所有n类加起来就是上面的式子。所以$A^{n+1}[i,j]$An+1[i,j]表示ij之间路径长为n+1的路径条数。