算法复杂度

算法复杂度是一个比较广泛的说法，用来描述算法在各种方面的复杂性和性能特征。它可以包括时间复杂度、空间复杂度以及其他与算法相关的方面。

时间复杂度（Time Complexity）

时间复杂度是算法复杂度的一部分，它衡量了算法在运行时所需的时间资源。时间复杂度通常以大O符号（O）表示，描述了算法的执行时间与输入规模之间的关系，以最坏情况为基准来评估。时间复杂度用于度量算法在不同输入条件下的性能。

时间复杂度是用来度量算法运行时间的一种方式。我们将使用函数T(n)来表示算法在输入规模为n时的运行时间。

O(f(n)) 表示算法的运行时间与输入规模n的某个函数f(n)成正比。这里是一些常见时间复杂度的详细解释和示例：

1. O(1)（常数时间复杂度）：无论输入规模如何增加，算法的执行时间都保持恒定。这通常是因为算法执行的操作数量是固定的。

int constantTimeAlgorithm(int[] array) {
    return array[0]; // 取第一个元素，不管数组多大，操作次数都相同
}

2. O(log n)（对数时间复杂度）：随着输入规模n的增加，算法的执行时间以对数方式增加。通常出现在分治或二分查找等算法中。

int binarySearch(int[] sortedArray, int target) {
    int left = 0, right = sortedArray.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (sortedArray[mid] == target) {
            return mid;
        } else if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

3. O(n)（线性时间复杂度）：随着输入规模n的增加，算法的执行时间线性增加。通常出现在遍历数组或列表等情况下。

int linearSearch(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            return i;
        }
    }
    return -1;
}

4. O(n log n)（线性对数时间复杂度）：通常出现在快速排序、归并排序等排序算法中。

void mergeSort(int[] array) {
    if (array.length <= 1) {
        return;
    }
    int mid = array.length / 2;
    int[] left = Arrays.copyOfRange(array, 0, mid);
    int[] right = Arrays.copyOfRange(array, mid, array.length);
    mergeSort(left);
    mergeSort(right);
    merge(array, left, right);
}

5. O(n^2)（二次时间复杂度）：随着输入规模n的增加，算法的执行时间呈二次方增加。通常出现在嵌套循环等情况下。

void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
 
        }
    }
}

6. O(2^n)（指数时间复杂度）：算法的运行时间随着输入规模的增加呈指数级增长。

随着输入规模的每个增加，算法的执行时间呈几何级增加，因此对于大规模输入，指数时间复杂度的算法会非常低效，甚至在实际应用中不可行。

指数时间复杂度通常以O(2^n)来表示，其中n是输入规模。这表示算法的运行时间随着n的每个单位增加，运行时间翻倍。

//斐波那契数列
public class ExponentialTimeExample {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = 10; // 修改n的值来观察不同规模下的运行时间
        long startTime = System.currentTimeMillis();
        int result = fibonacci(n);
        long endTime = System.currentTimeMillis();

        System.out.println("斐波那契数列第 " + n + " 项为: " + result);
        System.out.println("运行时间：" + (endTime - startTime) + " 毫秒");
    }
}

空间复杂度（Space Complexity）

空间复杂度也是算法复杂度的一部分，它度量了算法在运行时所需的内存资源。类似于时间复杂度，空间复杂度通常以大O符号（O）表示，描述了算法的内存占用与输入规模之间的关系，以最坏情况为基准来评估。空间复杂度用于度量算法在不同输入条件下的内存占用情况。

空间复杂度是用来度量算法在运行时所需的内存空间。同样使用大O符号（O）表示。

O(g(n)) 表示算法在输入规模n下所需的额外内存空间与某个函数g(n)成正比。以下是一些常见空间复杂度的详细解释和示例：

1. O(1)（常数空间复杂度）：算法的内存占用保持恒定，不随输入规模的增加而增加。

int constantSpaceAlgorithm(int[] array) {
    int sum = 0;
    for (int num : array) {
        sum += num;
    }
    return sum;
}

2. O(n)（线性空间复杂度）：算法的内存占用与输入规模n成正比。通常表示算法使用一个与输入规模相关的数据结构。

int[] linearSpaceAlgorithm(int n) {
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        result[i] = i;
    }
    return result;
}

3. O(n^2)（二次空间复杂度）：算法的内存占用与输入规模n的平方成正比。通常表示算法使用嵌套的数据结构。

int[][] quadraticSpaceAlgorithm(int n) {
    int[][] matrix = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = i + j;
        }
    }
    return matrix;
}

4. O(log n)（对数空间复杂度）：通常出现在递归算法中，递归调用的栈空间占用。

int recursiveFactorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * recursiveFactorial(n - 1);
}