16年408算法时间复杂度

16坎怙醣秸年408算法时间复杂度分情况:n=2^k;i从1到n,则需要计算k+1次也就是log(n)+1.n不等于2的某方则恰好少计算一次..计算次数为log(n).平均复杂度O(log(n))。

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

常数时间：

一个例子是访问数组中的单个元素，因为访问它只需要一条指令。但是，找到无序数组中的最小元素则不是，因为这需要遍历所有元素来找出最小值。这是一项线性时间的操作，或称时间。但如果预先知道元素的数量并假设数量保持不变，则该操作也可被称为具有常数时间。

虽然被称为“常数时间”，运行时间本身并不必须与问题规模无关，但它的上界必须是与问题规模无关的确定值。举例，“如果a > b则交换a、b的值”这项操作，尽管具体时间会取决于条件“a > b”是否满足，但它依然是常数时间，因为存在一个常量t使得所需时间总不超过t。