1.何為常數(shù)時(shí)間的操作？
2.如何確定算法流程的時(shí)間復(fù)雜度？
3.如何確定算法流程的總操作數(shù)量與樣本數(shù)量之間的表達(dá)式關(guān)系？
4.常見的時(shí)間復(fù)雜度
5.認(rèn)識(shí)異或運(yùn)算
6.為什么要手?jǐn)]數(shù)據(jù)結(jié)構(gòu)算法？

1.何為常數(shù)時(shí)間的操作？

如果一個(gè)操作的執(zhí)行時(shí)間不以具體樣本量為轉(zhuǎn)移，每次執(zhí)行時(shí)間都是固定時(shí)間。稱遮掩你的操作為常數(shù)時(shí)間的操作
例如，數(shù)組取數(shù)，數(shù)組下標(biāo)取數(shù)，是取固定地址的偏移量取值，取數(shù)耗時(shí)T和這個(gè)數(shù)的大小，數(shù)組下標(biāo)的大小無關(guān)。
常見的常數(shù)時(shí)間操作

• 常見的算術(shù)運(yùn)算（+ , - , * , / , %等）
• 常見的位運(yùn)算（>> , >>> , << , | , & , ^ 等）
• 賦值，比較，自增，自減操作等
• 數(shù)組尋址操作

總之：執(zhí)行時(shí)間固定的操作都是常數(shù)時(shí)間操作。
反之：執(zhí)行時(shí)間不固定的操作都不是常數(shù)時(shí)間操作。

1.如何確定算法流程的時(shí)間復(fù)雜度？

當(dāng)完成了表達(dá)式的建立，只要把最高階項(xiàng)留下即。低階項(xiàng)都去掉，高階的系數(shù)也去掉。
記作：O(忽略掉系數(shù)的高階項(xiàng))

3.如何確定算法流程的總操作數(shù)量與樣本數(shù)量之間的表達(dá)式關(guān)系？

1，想想該算法流程所處理的數(shù)據(jù)狀況，要按照最差情況來。
2，把整個(gè)流程徹底拆分為一個(gè)個(gè)基本動(dòng)作，保證每個(gè)動(dòng)作都是常數(shù)的操作。
3，如果數(shù)據(jù)量為N，看看基本動(dòng)作的數(shù)量與N是什么關(guān)系。

4.常見的時(shí)間復(fù)雜度

排名從好到差：

• O(1)
• O(logN)
• O(N)
• O(N * logN)
• O(N^2) O(N^3) O(N^4) O(N^5) ... O(N^k)
• O(2^N) O(3^N) O(4^N) O(5^N) O(k^N)
• O(N!)

5.認(rèn)識(shí)異或運(yùn)算

同或運(yùn)算：--
異或運(yùn)算：可以看作是無進(jìn)位的加法器。滿足交換律和結(jié)合律
案例1：快速找出一個(gè)數(shù)組中個(gè)數(shù)為奇數(shù)的那個(gè)數(shù)，并返回他

/**
 * 快速找出一個(gè)數(shù)組中個(gè)數(shù)為奇數(shù)的那個(gè)數(shù)，并返回。（只有一個(gè)奇數(shù)）
 * @author Tara
 * @implNote
 */
public class Pra4 {
    public static void main(String[] args) {
        int[] arr = new int[]{5,2,3,4,5,2,3,4,5,6,2,3,4,5,1,2,3,4,5,6,4,4,2,23,4,2,1,23,4};
        int a = 0;
        for (int i=0;i<arr.length;i++){
            a^=arr[i];
        }
        System.out.println(a);
    }
}

案例2：快速取出一個(gè)數(shù)二進(jìn)制最后一位1 ： N & （~N + 1）

/**
 * 快速取出一個(gè)數(shù)二進(jìn)制最后一位1 ：  N & （~N + 1），去除的數(shù)為1，2，4，8，16，32，64，128，256，。。。。
 * 例如 24 <==>11000,要取出1000（十進(jìn)制8）,
 * @author Tara
 * @implNote
 */
public class Pra5 {

    public static void main(String[] args) {
        int a = 24;
        System.out.println(a & (~a+1));

        for (int i = 0; i < 500; i++) {
            int b = i;
            System.out.print((b & (~b+1))+",");
        }
    }
}

案例3：一個(gè)數(shù)組中有兩種數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到并打印這兩種數(shù)？

/**
 * 一個(gè)數(shù)組中有兩種數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到并打印這兩種數(shù)？
 * @author Tara
 * @implNote
 */
public class Pra6 {

    public static void main(String[] args) {

        int arr[] = new int[]{0,1,2,3,4,5,1,2,3,4,5,0,2,4,5,6};
        printOddNums(arr);
    }

    private static void printOddNums(int[] arr) {
        // 所有數(shù)做異或操作
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor^=arr[i];
        }
        // 去除num左右側(cè)的1
        int rightOne = eor & (~eor+1);

        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & rightOne) == rightOne){
                rightOne^=arr[i];
            }
        }
        System.out.println("第一個(gè)數(shù)是"+rightOne +"第二個(gè)數(shù)是"+(eor^rightOne));
    }
}

案例4：將10進(jìn)制數(shù)轉(zhuǎn)成二進(jìn)制，找出其中有多少個(gè)1

/**
 * 將10進(jìn)制數(shù)轉(zhuǎn)成二進(jìn)制，找出其中有多少個(gè)1
 * @author Tara
 * @implNote
 */
public class Pra7 {

    public static void main(String[] args) {
        int N = 13257423;
        findCounts(N);
    }

    private static void findCounts(int n) {
        // 計(jì)數(shù)
        int count = 0;
        //每次都抹去最后一個(gè)1
        while (n >0){
            int rithtOne = n & (~n +1);
            //抹掉最后一個(gè)1
            n^=rithtOne;
            //思考，為什么抹掉最后一個(gè)1，用異或，不用-rightOne ???  答：因?yàn)槿绻鸑為負(fù)數(shù)的時(shí)候，會(huì)出問題。
            count++;
        }
        System.out.println("有"+count);
    }
}

6.為什么要手?jǐn)]數(shù)據(jù)結(jié)構(gòu)算法？

1.算法與語言無關(guān)；
2.語言提供的api是有限的，當(dāng)有新功能api不提供就需要改寫
3.任何軟件工具的底層都是基本的算法與數(shù)據(jù)結(jié)構(gòu)，這個(gè)是繞不過去了。