只从数组第2n-1(n 是数组长度)个元素开始倒着往前处理。
最后一层节点数大约n/2，因为是叶子节点，所以对其操作就只是看了一眼，操作数为1。
倒数第二层节点数大约n/4，操作是看一眼加上一次交换，操作数为2。
同理，倒数第三层节点数为n/8，操作数为3。
写出总的复杂度公式：
\(\mathrm{T}\left( \mathrm{n} \right) =\frac{\mathrm{n}}{2}\times 1+\frac{\mathrm{n}}{4}\times 2+\frac{\mathrm{n}}{8}\times 3+\mathrm{……}\)
利用错位相减法可以估计一下复杂度
\[\mathrm{T}\left( \mathrm{n} \right) =\frac{\mathrm{n}}{2}\times 1+\frac{\mathrm{n}}{4}\times 2+\frac{\mathrm{n}}{8}\times 3+\frac{\mathrm{n}}{16}\times 4+\mathrm{……} \\ 2\mathrm{T}\left( \mathrm{n} \right) =\frac{\mathrm{n}}{2}\times 2+\frac{\mathrm{n}}{2}\times 2+\frac{\mathrm{n}}{4}\times 3+\frac{\mathrm{n}}{8}\times 4+\mathrm{……} \\ \mathrm{T}\left( \mathrm{n} \right) =\mathrm{n}+\frac{\mathrm{n}}{2}+\frac{\mathrm{n}}{4}+\frac{\mathrm{n}}{8}+\mathrm{……} \\ \approx \mathrm{O}\left( \mathrm{n} \right) \]