如何判断时间复杂度是否为O（logn）

Answer 1

判断如下：

1、对数时间的算法是非常有效的，因为每增加一个输入，其所需要的额外计算时间会变小。

2、递归地将字符串砍半并且输出是这个类别函数的一个简单例子。它需要O（log n）的时间因为每次输出之前我们都将字符串砍半。 这意味着，如果我们想增加输出的次数，我们需要将字符串长度加倍。

扩展资料：

一、幂对数时间：对于某个常数k，若算法的T(n) = O((logn))，则称其具有幂对数时间。例如，矩阵链排序可以通过一个PRAM模型。被在幂对数时间内解决。

二、线性对数时间：若一个算法时间复杂度T(n) = O(nlog n)，则称这个算法具有线性对数时间。因此，从其表达式我们也可以看到，线性对数时间增长得比线性时间要快，但是对于任何含有n，且n的幂指数大于1的多项式时间来说，线性对数时间却增长得慢。

三、数据的逻辑结构指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

1、集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系。

2、线性结构：数据结构中的元素存在一对一的相互关系。

3、树形结构：数据结构中的元素存在一对多的相互关系。

4、图形结构：数据结构中的元素存在多对多的相互关系。

参考资料来源：百度百科-时间复杂度

参考资料来源：百度百科-数据结构

Answer 2

最直观的判断就是程序中采用了二分，且二分后只运算数据的一半。但如果两部分都运算的话，时间复杂度就是O(nlogn)了。其实不一定是二分，只不过二分比较常用罢了