数据结构第02节：算法复杂度

第2小节：课程基础概念 - 算法复杂度

在Java编程语言中，理解和应用算法复杂度的概念是非常重要的。下面将结合Java代码来展开叙述算法复杂度的各个方面。

2.1 算法复杂度的定义

算法复杂度通常用大O符号来表示。例如，一个简单的打印数组元素的Java方法可能具有O(n)的时间复杂度，其中n是数组的长度。

public void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]);
    }
}

2.2 时间复杂度

时间复杂度描述了算法执行时间与输入规模的关系。以下是不同时间复杂度的示例：

• 常数时间复杂度 O(1)：无论输入大小如何，执行时间都是固定的。

public void printMessage() {
    System.out.println("Hello, World!");
}

• 线性时间复杂度 O(n)：执行时间与输入规模成正比。

public void sumArray(int[] array) {
    int sum = 0;
    for (int num : array) {
        sum += num;
    }
}

• 平方时间复杂度 O(n^2)：通常出现在嵌套循环中。

public void printPairs(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            System.out.println("Pair: " + array[i] + ", " + array[j]);
        }
    }
}

2.3 空间复杂度

空间复杂度描述了算法执行过程中所需的存储空间量。例如，以下方法的空间复杂度是O(n)，因为它创建了一个与输入数组相同大小的新数组。

public int[] reverseArray(int[] array) {
    int[] reversed = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        reversed[i] = array[array.length - 1 - i];
    }
    return reversed;
}

2.4 理解大O符号

大O符号关注算法的增长趋势，忽略常数因子和低阶项。例如，如果一个算法的时间复杂度是3n^2 + 2n + 1，我们通常简化为O(n^2)。

2.5 常见时间复杂度分类

• 对数时间复杂度 O(log n)：通常与二分搜索相关。

public int binarySearch(int[] array, int target) {
    int low = 0, high = array.length - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1; // 使用无符号右移代替除以2
        if (array[mid] == target) return mid;
        else if (array[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

• 指数时间复杂度 O(2^n)：如暴力搜索算法。

public boolean hasAllCharacters(String haystack, String needle) {
    if (haystack.length() < needle.length()) return false;
    for (int i = 0; i <= haystack.length() - needle.length(); i++) {
        if (matches(haystack.substring(i), needle)) return true;
    }
    return false;
}

private boolean matches(String a, String b) {
    if (a.length() != b.length()) return false;
    for (int i = 0; i < a.length(); i++) {
        if (a.charAt(i) != b.charAt(i)) return false;
    }
    return true;
}

2.6 算法复杂度的比较

比较不同算法的复杂度可以帮助我们选择在特定情况下更高效的算法。

2.7 算法复杂度的计算

通过分析代码中的循环和递归调用，我们可以计算算法的复杂度。

2.8 算法复杂度的实际意义

在实际编程中，选择具有较低复杂度的算法可以显著提高程序的性能。

2.9 算法优化

通过优化算法逻辑和选择合适的数据结构，我们可以降低算法的复杂度。

2.10 练习和应用

通过实际编写和分析代码，学生可以加深对算法复杂度概念的理解，并学会如何在实际编程中应用这些知识。

以下是针对不同时间复杂度类别的Java代码示例，以帮助理解每种复杂度类别的特点：

常数时间复杂度：O(1)

常数时间复杂度意味着无论输入数据的大小如何，算法的执行时间都是固定的。

public void constantTimeOperation() {
    int result = 42; // 无论输入大小，结果都是常数时间操作
    System.out.println(result);
}

对数时间复杂度：O(log n)

对数时间复杂度通常与二分搜索算法相关，每次迭代都将搜索空间减半。

public int binarySearch(int[] array, int target) {
    int low = 0;
    int high = array.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

线性时间复杂度：O(n)

线性时间复杂度意味着算法的执行时间与输入数据的规模成正比。

public void linearTimeOperation(int[] array) {
    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}

线性对数时间复杂度：O(n log n)

线性对数时间复杂度常用于高效的排序算法，如快速排序或归并排序。

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

private void merge(int[] array, int leftStart, int leftEnd, int rightEnd) {
    // 实现归并逻辑
}

平方时间复杂度：O(n^2)

平方时间复杂度常见于简单排序算法，如冒泡排序。

public void bubbleSort(int[] array) {
    boolean swapped;
    for (int i = 0; i < array.length - 1; i++) {
        swapped = false;
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

指数时间复杂度：O(2^n)

指数时间复杂度通常出现在暴力搜索算法中，例如解决子集问题。

public void printAllSubsets(boolean[] subset, int i, int[] set, int n) {
    if (i == n) {
        for (int j = 0; j < n; j++) {
            if (subset[j]) {
                System.out.print(set[j] + " ");
            }
        }
        System.out.println();
        return;
    }
    subset[i] = true;
    printAllSubsets(subset, i + 1, set, n);
    subset[i] = false;
    printAllSubsets(subset, i + 1, set, n);
}

阶乘时间复杂度：O(n!)

阶乘时间复杂度通常出现在需要考虑所有排列的问题中，如旅行商问题。

public void permute(String str, int l, int r) {
    if (l == r) {
        System.out.println(str);
    } else {
        for (int i = l; i <= r; i++) {
            str = swap(str, l, i);
            permute(str, l + 1, r);
            str = swap(str, l, i); // backtrack
        }
    }
}

public String swap(String a, int i, int j) {
    char temp;
    char[] charArray = a.toCharArray();
    temp = charArray[i];
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return String.valueOf(charArray);
}

这些示例展示了不同时间复杂度在实际代码中的体现，帮助理解算法效率和性能之间的关系。