<rp id="wnpn7"><ruby id="wnpn7"></ruby></rp>
<progress id="wnpn7"><track id="wnpn7"><rt id="wnpn7"></rt></track></progress>
<ruby id="wnpn7"></ruby>
<ruby id="wnpn7"><blockquote id="wnpn7"><div id="wnpn7"></div></blockquote></ruby>

    1. <em id="wnpn7"><ruby id="wnpn7"><input id="wnpn7"></input></ruby></em>
      1. <button id="wnpn7"><acronym id="wnpn7"></acronym></button><button id="wnpn7"><acronym id="wnpn7"></acronym></button>

        <rp id="wnpn7"><acronym id="wnpn7"></acronym></rp>

        <li id="wnpn7"><object id="wnpn7"><u id="wnpn7"></u></object></li>
        VB.net 2010 視頻教程 VB.net 2010 視頻教程 python基礎視頻教程
        SQL Server 2008 視頻教程 c#入門經典教程 Visual Basic從門到精通視頻教程
        當前位置:
        首頁 > 編程開發 > c#教程 >
        • 1800字普林斯頓大學課程濃縮筆記:程序員必知的算法之查找和排序算法

        本站最新發布   C#從入門到精通
        試聽地址  
        http://www.squ68.com/eschool/CSharpxin3721/

         
         
        1 兩類經典算法
         
         

        在這一章節,考慮經典的算法:查找和排序,以及具體的應用。

         

        老生常談,偶爾遇到闡述這兩類問題相關的極好素材,它們結合示意圖,言簡意賅,清晰明了。故分享出來。

         

         
         
        2 猜數字游戲
         
         

        二分查找還是相對容易理解的,我們的目標是準確無誤地寫出其代碼。為此先從原理理解透二分查找,在游戲 "20個問題"中,你的任務是猜出一個神秘的數字,它位于0~n-1共n個之內。

         

        簡化起見,我們假定n是偶數,問題的問答形式是這樣:

        Q: “我猜神秘數為 i”

        A:“你猜的數字 i 大于或等于 真正的神秘數77

         

        這個過程,參考如下示意圖:

         

         

        此處,一個有效的策略是維護一個間隔,它包含 x ,猜的數位于這個區間中間,以下 Questions類實現了這個策略。

         

         1public class Questions {
         2
         3    // invariant: answer is in [lo, hi)
         4    public static int search(int lo, int hi) {
         5        if ((hi - lo) == 1return lo;
         6        int mid = lo + (hi - lo) / 2;
         7        StdOut.printf("Is it less than %d?  ", mid);
         8        if (StdIn.readBoolean()) 
         9            return search(lo, mid);
        10        else                     
        11            return search(mid, hi);
        12    }
        13
        14    public static void main(String[] args) {
        15        int k = Integer.parseInt(args[0]);
        16        int n = (int) Math.pow(2, k);
        17        StdOut.printf("Think of an integer between %d and %d\n"0, n-1);
        18        int secret = search(0, n);
        19        StdOut.printf("Your number is %d\n", secret);
        20    }
        21
        22}
        

         

        這里面有個細節,mid = lo + (hi-lo)/2,這樣寫是為了防止發生溢出。

         

        這個猜數字的游戲就是二叉搜索的一個經典例子。

         

         
         
        分析二分查找
         
         

        3.1 時間復雜度 

        在上面這個猜謎游戲中,使用了二分查找,因為沒迭代一次,求解區間減為原來一半,因此二分查找的時間復雜度為 lgn.

         

        3.2 二分查找退化為線性搜索 

        如果我們不采取上面的猜數字策略,依次1,2,3,...n-1,直到命中數字,這就是 brute-force 暴力算法,此時的時間復雜度為 n.

         

        3.3 二進制表示  

        某個數轉化為二進制表示(代碼見下)的過程與二分查找很相似,例如,神秘數為77,然后猜題的回答為:no yes yes no no yes no ,則二進制表示為 1001101,二進制表示恰好為 77.

         

         1public class Binary { 
         2    public static void main(String[] args 3
         4        // read in the command-line argument
         5        int n = Integer.parseInt(args[0]);
         6
         7        // set power to the largest power of 2 that is <= n
         8        int power = 1;
         9        while (power <= n/2) {
        10            power *= 2;
        11        }
        12
        13        // check for presence of powers of 2 in n, from largest to smallest
        14        while (power > 0) {
        15
        16            // power is not present in n 
        17            if (n < power) {
        18                System.out.print(0
              
        
        
        
          
        相關教程
                
        免费看成年人视频大全_免费看成年人视频在线观看