统计

  • 随笔 - 50
  • 文章 - 42
  • 评论 - 147
  • 引用 - 0

留言簿(6)

随笔分类

文章分类

Link

搜索

  •  

积分与排名

  • 积分 - 160080
  • 排名 - 161

最新评论

阅读排行榜

评论排行榜

寻找k大

 自己写的寻找数组中第k大元素的函数,采用二分查找法,平均时间复杂度O(logN),有更好的方法欢迎指正

 感谢 双杯献酒 同学指正,我重新思考了一下次算法的时间复杂度
理想情况下如果每次都正好分到中间的话,每次比较的次数就是公比为0.5的等比数列,也就得到
T(N)=a1(1-q^n)/(1-q) =N(1-0.5^(logN))/0.5=2N-0,5^(logN-1)
当N→∞时,得平均时间复杂度为O(N)
但是本算法的最坏情况确实O(N^2)

/************************************************************************/
/* find the k bigger number in the array, using Bisection method
/* Contact:lyi.tech@gmail.com
/* 2011-3-10
/***********************************************************************
*/

int findKBiggest(int *array,int begin,int end,int k);
int nonrecursive_FindKBiggest(int *array,int length,int k);
void switch2(int *a,int *b);
//************************************
// Method:    findKBiggest
// FullName:  findKBiggest
// Access:    public 
// Returns:   int
// Qualifier:
// Parameter: int * array
// Parameter: int length
// Parameter: int k
// Parameter: int * k_value 
//                the K biggest number,the biggest number is labeled by 1
//************************************
int findKBiggest(int *array,int length,int k,int *k_value)
{
    
if (k>length||k<1||length<1)
        
return -1;
    
else 
    
{
        
//*k_value=findKBiggest(array,0,length-1,k);
        *k_value=nonrecursive_FindKBiggest(array,length,k);
        
return 0;
    }

}


//************************************
// Method:    recursive method
// FullName:  findKBiggest
// Access:    public 
// Returns:   the K biggest number,the biggest number is labeled by 1
// Qualifier:
// Parameter: int * array
// Parameter: int begin
// Parameter: int end
// Parameter: int k base on 1
//************************************
int findKBiggest(int *array,int begin,int end,int k)
{
    
int tmpbegin=begin;
    
int tmpend=end;
    
int *tmp=array+begin++;
    
int length=end-begin+1;
    
while (1)
    
{
        
while ((*(array+begin) >= *tmp)&&(begin<tmpend))
            begin
++;
        
while ((*(array+end) < *tmp)&&(end>tmpbegin))
            end
--;
        
if (begin<end)
        
{
            switch2(array
+begin,array+end);
        }

        
else
        
{
            switch2(tmp,array
+end);
            
break;
        }

    }

    
if (end+1==k)
        
return *tmp;
    
else if(end+1<k)
        
return findKBiggest(array,end+1,tmpend,k);
    
else
        
return findKBiggest(array,tmpbegin,end-1,k);

}


void switch2(int *a,int *b)
{
    
if (a!=b)
    
{
        
*a=*a+*b;
        
*b=*a-*b;
        
*a=*a-*b;
    }

}


//************************************
// Method:    nonrecursive method
// FullName:  nonrecursive_FindKBiggest
// Access:    public 
// Returns:   the K biggest number,the biggest number is labeled by 1
// Qualifier:
// Parameter: int * array
// Parameter: int length
// Parameter: int k
//************************************
int nonrecursive_FindKBiggest(int *array,int length,int k)
{
    
int begin=0,end=length-1;
    
int tmpbegin,tmpend;
    
int posnow=0;
    
while (1)
    
{    
        tmpbegin
=begin+1;
        tmpend
=end;
        
while (1)
        
{
            
while (*(array+tmpbegin) >= *(array+begin) && tmpbegin<end)
                tmpbegin
++;
            
while (*(array+tmpend) < *(array+begin) && begin < tmpend)
                tmpend
--;
            
if (tmpbegin<tmpend)
            
{
                switch2(array
+tmpbegin,array+tmpend);
            }

            
else
            
{
                switch2(array
+begin,array+tmpend);
                
break;
            }

        }

        
if (k==tmpend+1)
            
break;
        
else if(k>tmpend+1)
            begin
=tmpend+1;
        
else
            end
=tmpend-1;
    }

    
return *(array+tmpend);
}

 

 

 

 

posted on 2011-03-10 12:38 pear_li 阅读(1919) 评论(10)  编辑 收藏 引用 所属分类: Algorithm

评论

# re: 寻找k大 2011-03-10 14:03 gbb21

Please be attention to your ugly Chiglish naming in the code.
  回复  更多评论    

# re: 寻找k大[未登录] 2011-03-10 14:23 pear_li

@gbb21
see it or not,then shut fu_cking up
  回复  更多评论    

# re: 寻找k大[未登录] 2011-03-10 14:43 R

BFPRT.
  回复  更多评论    

# re: 寻找k大 2011-03-10 17:51 hook

楼上说的没错,请参考:
http://en.wikipedia.org/wiki/Selection_algorithm
  回复  更多评论    

# re: 寻找k大[未登录] 2011-03-10 22:37 pear_li

@hook
貌似和我算法很相似
  回复  更多评论    

# re: 寻找k大[未登录] 2011-03-11 09:14 vincent

怎么得出的logN的复杂度。。
  回复  更多评论    

# re: 寻找k大 2011-03-11 11:04 双杯献酒

对于数据Data[N]
如果已经排序,则第k大的元素就是Data[k],何须查找?复杂度O(1)
如果尚未排序,就不能使用二分查找.
如果要先排序, 通用的基于比较排序最低复杂度也是O(N*logN)
最经典的BFPRT算法复杂度也是O(N), 直观来说,要确定第k大的元素,每个数据总要过一遍吧. 那复杂度也至少是O(N), 要在O(logN)找到是不可能的.
不明白作者怎么弄的.
  回复  更多评论    

# re: 寻找k大 2011-03-11 21:46 pear_li

@双杯献酒
说的不错
  回复  更多评论    

# re: 寻找k大 2011-03-12 15:05 Devil Wang

有O(logN)的算法 。如果你看过算法 导论 关于 快排那部分的算法的话。

你要做的就是改造partition算法。
  回复  更多评论    

# re: 寻找k大[未登录] 2011-03-13 18:28 pear_li

@Devil Wang
这个真没有,如果有还请明示,那本书我看过。。。
  回复  更多评论    

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