computer 版 (精华区)

发信人: gutentag ( Bonjour && deeply in LOVE on the web ), 信区: program
标  题: Re: 找第n个最小数
发信站: 听涛站 (2001年10月15日21:45:38 星期一), 站内信件

我仔细考虑了一下这个最坏情况                                                    
以“比较次数”来计算的话：(j 指向的数每次总被交换至最后，每次递归最多交换一次)  
        最坏的比较次数为：(n-1)+(n-2)+...+1= (n-1)*(n-2)/2 ～ n^2               
    此时最坏的交换次数为：   1 +   1 +...+1=  n-1          ～ n                 
【Bonjour && deeply in LOVE on the web】  
以“交换次数”来计算，情况比较复杂：                                            
    先考虑一种极端的情况：(j 指向的数每次总被交换至中间)                        
    递归阶数  待处理的数组长度  最坏的交换次数  最坏的比较次数(与交换次数相等)  
        ０    n                 (n-1)           (n-1)              < n          
        １    (n-1)/2           (n-1)/2-1       (n-1)/2-1          < n/(2^1)    
        ２    ((n-1)/2-1)/2     ((n-1)/2-1)/2-1 ((n-1)/2-1)/2-1    < n/(2^2)    
        ·      ·              　·            　·                 ·         
        ·      ·              　·            　·                 ·         
        　      ·              　·            　·                 ·         
        ＋)     ２                １              １                 １         
     ————————————————————————————————————— 
               < 2n              < 2n            < 2n           = 2n-1 < 2n     

    综合前一种极端情况，交换次数有两个极端的值：n 和 < 2n
    其它的情况会不会出现更大的值，还不能确定，我估计不会。

    于是我具体的统计了一下 n 等于各值时所需最多的交换次数……

    
--

                春が来た、春が来た、どこに来た。
                山に来た、郷に来た、野にも来た。

※ 来源:·听涛站 tingtao.dhs.org·[FROM: 匿名天使的家]