复杂度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个数字，假设最小的数字就是第一个，用min保存。然后剩下n-1个数字和当前min比较，找到更小的就更新min值，得到最小的min值，如果不是第一个数字，就和第一个数字交换，就找出来第一小的值。然后再进行剩下的迭代。
第一次迭代，比较次数为n-1；
第二次迭代，比较次数n-2；
第n-1次迭代，比较次数1；
假设T（n）表示选择排序的复杂度，c表示每次迭代中其他操作的总数（如赋值和比较）
T（n）=（n-1）+C+（n-2）+C+.......+2+c+1+c
=n(n-1)/2+(n-1)c
=O(n的平方)

• 3. 汉诺塔

• 4.斐波那契数

效率不高，我们使用动态编程方法实现斐波那契数列。效率为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.最大公约数

1）算法一：穷举 O（n）

2）改进，从两个数中相对小的数向下找。但最坏情况时间复杂度还是O(n)

4)欧几里得算法，递归思想，O（logn）

图片.png

常用的递推关系

• 6.寻找素数

1)算法一：时间复杂度O（n*sqrt（n））

2）算法二：埃拉托色尼筛选算法

• 7.回溯法解决八皇后问题

八皇后问题：在一个棋盘的每一行放置一个皇后棋子，不存在在同一列或者在对角线的两个棋子。

1）从第一行开始为每一行寻找合适的位置
2）如果找到了位置，则继续为下一行搜索位置。
3）如果没有找到位置，回溯到前一行，在前一行之前位置之后搜索一个新的位置。
4）如果算法回溯到第一行且不能在该行找到一个新的位置，则不能找到方案。

public class text1_回溯法解决八皇后问题 {
    private static final int SIZE=8;
    //用queens数组来存每一行放置的位置
    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("没找到");
    }

}