可以很容易地看到（或用归纳法正式证明），对于从1到n的k值，T（n）是1 / k的和。这是 n
次谐波数，H n = 1 + 1/2 + 1/3 + …
+ 1 / n。
渐近地，谐波数以log（n）的顺序增长。这是因为从1到n，该和的值接近于1 / x的整数，该整数等于n的自然对数。实际上，H n = ln（n）+γ+O（1/n），其中γ是一个常数。据此，容易证明T（n）＝Θ（log（n））。
可以很容易地看到（或用归纳法正式证明），对于从1到n的k值，T（n）是1 / k的和。这是 n
次谐波数，H n = 1 + 1/2 + 1/3 + …
+ 1 / n。
渐近地，谐波数以log（n）的顺序增长。这是因为从1到n，该和的值接近于1 / x的整数，该整数等于n的自然对数。实际上，H n = ln（n）+γ+O（1/n），其中γ是一个常数。据此，容易证明T（n）＝Θ（log（n））。
名师互学网 版权所有 (c)2021-2022 ICP备案号：晋ICP备2021003244-6号
