復雜度O允許忽略非主導部分（n-1中的-1）梯醒，并強調重要部分（n-1中的n）

• 1. 線性查找

最壞情況：比較n次妨猩，O(n)
最好情況：比較1次担敌，O(1)
平均情況：(1+2+...+n)/n=(1+n)n/2/n=(1+n)/2,可以忽略1，就是O(n/2)

• 2. 選擇排序

對于一次迭代堪夭，n個數(shù)字咏删，假設最小的數(shù)字就是第一個惹想，用min保存。然后剩下n-1個數(shù)字和當前min比較督函，找到更小的就更新min值嘀粱，得到最小的min值激挪，如果不是第一個數(shù)字，就和第一個數(shù)字交換草穆，就找出來第一小的值灌灾。然后再進行剩下的迭代。
第一次迭代悲柱，比較次數(shù)為n-1锋喜；
第二次迭代，比較次數(shù)n-2豌鸡；
第n-1次迭代嘿般，比較次數(shù)1；
假設T（n）表示選擇排序的復雜度涯冠，c表示每次迭代中其他操作的總數(shù)（如賦值和比較）
T（n）=（n-1）+C+（n-2）+C+.......+2+c+1+c
=n(n-1)/2+(n-1)c
=O(n的平方)

• 3. 漢諾塔

• 4.斐波那契數(shù)

效率不高炉奴，我們使用動態(tài)編程方法實現(xiàn)斐波那契數(shù)列。效率為O(n)

 private static long fib2(int index){
        long f0=0;
        long f1=1;
        long f2=1;
        if(index==0)return f0;
        if (index==1)return f1;
        if (index==2)return f2;
        for(int i=3;i<=index;i++){
            f0=f1;
            f1=f2;
            f2=f0+f1;
        }
        return f2;
    }

• 5.最大公約數(shù)

1）算法一：窮舉 O（n）

2）改進蛇更，從兩個數(shù)中相對小的數(shù)向下找瞻赶。但最壞情況時間復雜度還是O(n)

4)歐幾里得算法，遞歸思想豆混，O（logn）

圖片.png

常用的遞推關系

• 6.尋找素數(shù)

1)算法一：時間復雜度O（n*sqrt（n））

2）算法二：埃拉托色尼篩選算法

• 7.回溯法解決八皇后問題

八皇后問題：在一個棋盤的每一行放置一個皇后棋子篓像，不存在在同一列或者在對角線的兩個棋子。

1）從第一行開始為每一行尋找合適的位置
2）如果找到了位置皿伺，則繼續(xù)為下一行搜索位置员辩。
3）如果沒有找到位置，回溯到前一行鸵鸥，在前一行之前位置之后搜索一個新的位置屈暗。
4）如果算法回溯到第一行且不能在該行找到一個新的位置，則不能找到方案脂男。

public class text1_回溯法解決八皇后問題 {
    private static final int SIZE=8;
    //用queens數(shù)組來存每一行放置的位置
    int []queens={-1,-1,-1,-1,-1,-1,-1,-1};

    //回溯算法
    private  boolean search() {
        int row=0;
        while (row>=0&&row<SIZE){
            //找到第i行放置的位置
            int k=findPosition(row);
            //說明沒有找到位置，要回溯到上一行
            if(k==-1){
                //在回溯上一行之前种呐，要將當前行的值恢復初始值-1宰翅，重新找
                queens[row]=-1;
                row--;
            }
            else{
               queens[row]=k;
               row++;
            }

        }
        //如果放置一遍,回溯到第一行，并且第一行也沒找到,i--就變成1了
        if(row==-1)
            return false;
        else
            return true;

    }

    private int findPosition(int row) {
        //每次放置的位置爽室，從上次位置的下一個開始
        int start=queens[row]+1;
        for(int col=start;col<SIZE;col++) {
            //判斷row行汁讼，col列的位置是否可行
            if (isvalid(row, col))
                return col;
        }
        return -1;
    }

    private boolean isvalid(int row, int col) {
        //判斷前面的每一行的queen[row-i]和col是否相等，相等表示在同一列
        //判斷前面的每一行的queen[row-i]和col-i是否相等，相等表示在左對角線
        //判斷前面的每一行的queen[row-i]和col+i是否相等嘿架，相等表示在右對角線
       for(int i=1;i<=row;i++){
           if(queens[row-i]==col||queens[row-i]==col-i||queens[row-i]==col+i)
               return false;
       }
       return true;

    }


    @Test
    public void test(){
        if(search())
            for (int i:queens)
                System.out.print(i+" ");
        else
            System.out.print("沒找到");
    }

}