算法基础一

认识时间复杂度

常数时间的操作

一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。

时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。具体

来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，

进而总结出常数操作数量的表达式。

在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那

么时间复杂度为O(f(N))。

评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行

时间，也就是“常数项时间”。

选择排序、冒泡排序细节与复杂度分析

时间复杂度O(N^2)，额外空间复杂度O(1)

选择排序

它的基本思想是每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。

 public class selectionSort {
    public static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void selection(int arr[]) {
        int len = arr.length;

        for (int i = 0; i < len; i++) {
            int tempMaxInt = i;//假设未排序部分的最左端是最大值
            for (int j = i + 1; j < len; j++) {
                if (arr[tempMaxInt] < arr[j]) {
                    tempMaxInt = j;//遍历未排序部分,发现更大的值,记录下最大的值索引
                }
            }
            swap(arr, tempMaxInt, i);//把未排序部分得最大值和已排序部分得下一个,也即是未排序部分得第一个交换
            //然后排序部分向右扩
        }
    }

    public static void main(String args[]) {
        int arr[] = { 5, 4, 1, 3, 2 };
        selection(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 冒泡排序

 public class bubbleSort {
    public static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void _bubbleSort(int arr[]) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            boolean flag = false;
            for (int j = len - 1; j > i; j--) {
                if (arr[j] > arr[j - 1]) {
                    swap(arr, j - 1, j);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = { 5, 4, 1, 3, 2 };
        _bubbleSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

插入排序

 它的核心思想是将未排序部分的元素逐个插入到已排序部分的正确位置。

 public class insertSort {

    // 插入排序方法
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // 从第二个元素开始，逐个插入到已排序部分
        for (int i = 1; i < n; i++) {
            int key = arr[i]; // 当前需要插入的元素
            int j = i - 1;

            // 将比 key 大的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            // 插入 key 到正确位置
            arr[j + 1] = key;
        }
    }

    // 打印数组的方法
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 主方法：测试插入排序
    public static void main(String[] args) {
        int[] arr = { 12, 11, 13, 5, 6 }; // 待排序的数组

        System.out.println("排序前的数组:");
        printArray(arr);

        // 调用插入排序方法
        insertionSort(arr);

        System.out.println("排序后的数组:");
        printArray(arr);
    }
}

 二分查找

它的核心思想是通过不断缩小查找范围，将查找时间复杂度从 O(n) 降低到 O(log n)

 public class BinarySearch {

    // 二分查找方法
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // 计算中间位置
            if (arr[mid] == target) {
                return mid; // 找到目标值，返回索引
            } else if (arr[mid] < target) {
                left = mid + 1; // 目标值在右半部分
            } else {
                right = mid - 1; // 目标值在左半部分
            }
        }
        return -1; // 未找到目标值
    }

    // 主方法：测试二分查找
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11}; // 有序数组
        int target = 7; // 目标值

        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("目标值 " + target + " 的索引是: " + result);
        } else {
            System.out.println("目标值 " + target + " 未找到");
        }
    }
}

对数器

它的核心思想是通过对比待测试算法和一个已知正确的算法（通常是一个暴力解法或标准库函数），在大量随机测试数据上运行，确保两者结果一致。

master公式(适用与分治类型的)

T(N) = a*T(N/b) + O(N^d)

a表示每次递归产生的子问题数量

b表示相对原问题缩小的比例 

O(N^d) 表示原问题分解为子问题以及合并子问题解所需的工作量