时间复杂度

时间复杂度 = while的循环次数

• 算法的基本操作执行次数是问题规模n的某一个函数，记作T(n)；
• 存在一个辅助函数f(n)，使得T(n)/f(n)当n趋向于无穷大时，他们的值是个不为零的常数，那f(n)就是T(n)的同数量级函数
• 这个算法的时间复杂度是O(f(n))

同数量级函数有：1、log2n、n、nlog2n、n平方、n三次方、2的n次方、n的阶乘

例子

假设共n个数，那下一轮是n/2，再下一轮是n/4（即n/2²）...最后是n/(2的k次方)。其中k是循环的次数 故，要计算：n/(2的k次方) >= 1

解，得：n = (2的k次方)

k = logn