我要啦免费统计
O(n)时间O(1)辅助空间,循环移位


这一道,google的笔试题,网易也用过,学校的数据结构题目系统也有,之前我都是卡着机器出的

现在整理一下

一 3次翻转做法
/*about 循环移位
实例:abcdefgh 向左循环移位3位
     结果 defghabc

      1.abc做翻转  cba defgh

      2 defgh做翻转  cba  hgfed
   
      3.第二结果全部在做翻转    成为  defghabc   
*/

template<class T>
void reverse(T a[],int i,int j)
{
     
while(i < j)
     
{
             swap(a[i],a[j]);
             
++i;
             
--j;
     }

}



template
<class T>
void exch1(T a[],int n,int k)
{
     reverse(a,
0,k-1);
     reverse(a,k,n
-1);
     reverse(a,
0,n-1);
}

     reverse(a,0,k-1); //  k/2
     reverse(a,k,n-1); // (n-k)/2
     reverse(a,0,n-1); //  n/2
 为 k/2+(n-k)/2+k/2=n/2 + n/2  = n


二 ...


posted on 2009-11-26 12:40 阅读(1242) 评论(3)  编辑 收藏 引用 所属分类: algorithm

评论:
# re: O(n)时间O(1)辅助空间,循环移位 2009-11-28 11:29 | AutumWinter
reverse(a,0,k-1); // k/2
reverse(a,k,n-1); // (n-k)/2
reverse(a,0,n-1); // n/2
你的复杂度计算有点问题问题,上面每个复杂度都应该乘2,因为swap函数里面有两次移动操作
结果是k + (n - k) + n = 2n = O(n),与移动长度K无关,每个元素都移动两次。
如果直接移动的话相当于每个元素都移动了K次,复杂度是O(K*n)  回复  更多评论
  
# re: O(n)时间O(1)辅助空间,循环移位 2009-11-30 17:28 | cdy20
swap ,可以swap一次过,不同编译器吧
可以直接位运算 交换地址,

这个我把它认为是一次的,因为我们可以写成条表达式,至于编译器是否分析成几条,还是一条,我就不清楚的。这一次我明白你两次的说法

((1/2)*swap次数)

我在分析的时候只不过把一个过程写出来,晕。k都化掉了,肯定没关。
我只是想把问题简单化地分析

  回复  更多评论
  
# re: O(n)时间O(1)辅助空间,循环移位 2009-11-30 18:06 | cdy20
void reverse(T a[],int i,int j)
{
while(i < j)
{
swap(a[i],a[j]);
++i;
--j;
}
}
这个看成 是 (j-i)/2 次向下去整
再细化下去,也是带个常系数 x*((j-i)/2)
x=swap(你可以通常写法,三次) + i,j操作写法两次+最多加上函数调用开销



即使是k*n次,k这个属于一个小常数

我非常倒,估计不知不到,O()这个概念,
即使常数倍N 也是属于O(N)

翻转最坏情况,最坏n==k,这个算法3*N

这都是属于O(N)  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理