Reverse String 有 O(logn)的方法么？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Reverse String 有 O(logn)的方法么？

Reverse String 有 O(logn)的方法么？# JobHunting - 待字闺中

c*82015-03-01 08:03

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)的算法？谢啦。

x*g2015-03-01 08:03

2 楼

不懂帮顶~觉得怎么都要扫一遍呀

l*h2015-03-01 08:03

3 楼

题目是你的具体例子还是泛指reverse任意长的string?

s*x2015-03-01 08:03

4 楼

这么明显的最优也得O(n)的问题还在找更优解法。

n*n2015-03-01 08:03

5 楼

问是否有？回答没有不就可以了？

2)

【在 c****8 的大作中提到】

: 大家好，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)的算法？谢啦。

c*82015-03-01 08:03

6 楼

泛指任意长度的string

【在 l****h 的大作中提到】

: 题目是你的具体例子还是泛指reverse任意长的string?

c*82015-03-01 08:03

7 楼

我是觉得没有，我跟他说没有。他说再想想。最后我其实答了divide and conquer，因
为我实在想不到O(logn)的方法，最后他居然满意了。但是divide and conquer是O(n)
啊。

【在 n******n 的大作中提到】

: 问是否有？回答没有不就可以了？
:
: 2)