能否以O(logn)时间复杂度遍历数组？无需有序输出时能否O(log(n))访问全部元素？

嘿，咱来好好掰扯清楚你这俩问题！

答案是绝对不行。

咱得先搞明白时间复杂度的本质：O(logn)意味着操作次数只和n的对数成正比，比如n=1024时，log₂n才10次操作。但数组是线性存储的结构，“遍历”的核心就是要触达每一个元素——总共有n个元素，怎么可能用10次操作就覆盖1024个元素呢？这完全说不通。遍历必须访问所有元素，所以最少也得n次基础操作，时间复杂度的下限就是O(n)，O(logn)远远达不到这个要求。

答案还是不行。

不管你要不要按顺序输出，只要目标是“访问所有元素”，那每个元素都必须被读取至少一次。哪怕你乱着输出，也得先找到每个元素吧？这依然需要n次操作，时间复杂度还是O(n)。O(logn)的时间最多只能访问logn个元素，比如用二分查找每次只碰中间元素，跑下来也只能访问logn个点，根本没法覆盖全部n个元素。所以不管输出顺序如何，要访问所有元素，时间复杂度不可能低于O(n)。

内容的提问来源于stack exchange，提问作者user13956420