a**********2
发帖数: 340 | 1 不能用swap，只能用给定的function
reverse(i): reverse first i element in array.
有没有O(nlogn）解啊? |
f****4
发帖数: 1359 | 2 应该没有吧
假设存在O(nlgn)，则有
T(n) = 2T(n/2)+f(n)
需要f(n) = O(n)
考虑2n+1个数
n个1， n个3
3 3 3 3...3 1 1 1 1...1 2
用reverse()改成
1 1 1 1...1 2 3 3 3 3...3
需要 f(n) = n + n*( (n+1)+n) = O(n^2)
最后需要的run time 是O(n^2) |
a**********2
发帖数: 340 | 3 可能average是O(nlogn)就可以了吧
我当时给的解法就是O(n^2)
对i<- n to 1
找到1到i里面最大的值arr[j]然后reverse(j),reverse(i)
明显他不满意，后来说quicksort，选第一个或者最后一个做pivot好像不行，如果题目
改成reverse(i,j)就好了 |
f****4
发帖数: 1359 | 4 reverse(i,j){
reverse(j);
reverse(i);
reverse(j);
}
谁来分析一下avg？
【在 a**********2 的大作中提到】
: 可能average是O(nlogn)就可以了吧
: 我当时给的解法就是O(n^2)
: 对i<- n to 1
: 找到1到i里面最大的值arr[j]然后reverse(j),reverse(i)
: 明显他不满意，后来说quicksort，选第一个或者最后一个做pivot好像不行，如果题目
: 改成reverse(i,j)就好了
|
d*******d
发帖数: 2050 | 5 这里的reverse是算O(n)呢还是算O(1)呢? |
h*****3
发帖数: 1391 | |
f*********1
发帖数: 75 | 7 exchange(i,j){
reverse(i,j);
reverse(i+1,j-1);
}
so nlogn ?
【在 f****4 的大作中提到】
: reverse(i,j){
: reverse(j);
: reverse(i);
: reverse(j);
: }
: 谁来分析一下avg？
|
f****4
发帖数: 1359 | 8 给的是
reverse(i); // 0~i reverse
除非说是 reverse(i) O(1)
不然很怀疑有 nlgn
【在 f*********1 的大作中提到】
: exchange(i,j){
: reverse(i,j);
: reverse(i+1,j-1);
: }
: so nlogn ?
|
m****t
发帖数: 555 | 9 这个就是Bill Gates上大一的时候发表的一篇数学论文，关于翻松饼次数的上下界，其
实就是这种reverse排序次数的分析。有兴趣者可以找来读一下。 |
m****t
发帖数: 555 | 10 查了一下，这个问题叫做pancake sorting，在数学上来说并不简单，已经研究了几十
年。现在最好的结果是需要执行reverse的次数介于(15/14)n 和 (18/11)n之间。
http://en.wikipedia.org/wiki/Pancake_sorting |
q****x
发帖数: 7404 | 11 这里假定reverse(1)和reverse(100)代价相同？
【在 m****t 的大作中提到】
: 查了一下，这个问题叫做pancake sorting，在数学上来说并不简单，已经研究了几十
: 年。现在最好的结果是需要执行reverse的次数介于(15/14)n 和 (18/11)n之间。
: http://en.wikipedia.org/wiki/Pancake_sorting
|
f****4
发帖数: 1359 | 12 学习了～
【在 m****t 的大作中提到】
: 查了一下，这个问题叫做pancake sorting，在数学上来说并不简单，已经研究了几十
: 年。现在最好的结果是需要执行reverse的次数介于(15/14)n 和 (18/11)n之间。
: http://en.wikipedia.org/wiki/Pancake_sorting
|
