Reverse String 有 O(logn)的方法么?# JobHunting - 待字闺中
c*8
1 楼
大家好,reverse string: abcd --> dcba. 其实方法很简单,就是two pointers,一
个从头开始扫,一个从尾开始扫,然后swap就行。复杂度为:O(n)。但被问及是否可以
做到O(logn),我怎么想也没有想出O(logn)的方法,就算是divide and conquer 或者
类似 binary search的方法,最后的复杂度也是O(n)。因为递推公式是:T(n)=2T(n/2)
+1。
想问问大家有没有O(logn)的算法?谢啦。
个从头开始扫,一个从尾开始扫,然后swap就行。复杂度为:O(n)。但被问及是否可以
做到O(logn),我怎么想也没有想出O(logn)的方法,就算是divide and conquer 或者
类似 binary search的方法,最后的复杂度也是O(n)。因为递推公式是:T(n)=2T(n/2)
+1。
想问问大家有没有O(logn)的算法?谢啦。