数据结构第35节 性能优化 算法的选择

算法的选择对于优化程序性能至关重要。不同的算法在时间复杂度、空间复杂度以及适用场景上有着明显的差异。下面我将结合具体的代码示例，来讲解几种常见的算法选择及其优化方法。

示例 1: 排序算法

场景描述:

假设我们需要对一个整数数组进行排序。

算法选择:

对于较大的数据集，快速排序通常是一个不错的选择，因为它在平均情况下的时间复杂度为 O(n log n)。但对于小数据集，插入排序可能更优，因为它的常数因子较小。

代码示例:

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

示例 2: 查找算法

场景描述:

假设我们需要在一个有序数组中查找特定元素。

算法选择:

对于有序数组，二分查找是一个很好的选择，其时间复杂度为 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

示例 3: 动态规划

场景描述:

假设我们要解决斐波那契数列问题。

算法选择:

递归解决斐波那契数列问题会导致大量的重复计算。使用动态规划，我们可以存储中间结果，避免重复计算，从而将时间复杂度降低到 O(n)。

代码示例:

public class FibonacciDP {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

示例 4: 图算法 - Dijkstra 算法

场景描述:

假设我们需要找到图中两点之间的最短路径。

算法选择:

Dijkstra 算法是一个非常有效的单源最短路径算法，其时间复杂度为 O((V+E)log V)，其中 V 是顶点数，E 是边数。

代码示例:

import java.util.*;

public class DijkstraAlgorithm {
    public static void dijkstra(Map<Integer, Map<Integer, Integer>> graph, int startNode) {
        int[] distances = new int[graph.size()];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[startNode] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{startNode, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentNode = current[0];
            int distanceToCurrent = current[1];

            if (distanceToCurrent > distances[currentNode]) continue;

            for (Map.Entry<Integer, Integer> entry : graph.get(currentNode).entrySet()) {
                int neighbor = entry.getKey();
                int weight = entry.getValue();
                int distanceToNeighbor = distanceToCurrent + weight;

                if (distanceToNeighbor < distances[neighbor]) {
                    distances[neighbor] = distanceToNeighbor;
                    pq.offer(new int[]{neighbor, distanceToNeighbor});
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

以上示例展示了如何根据不同的问题选择合适的算法，以及如何通过算法优化来提高程序的性能。每种算法都有其特定的适用场景和性能特征，因此在实际应用中，应根据具体情况灵活选择。

当然，我们可以进一步扩展上述算法的代码示例，添加更多实用的功能和增强代码的健壮性。接下来，我将为每一个示例增加额外的方法和注释，以帮助更好地理解和使用这些算法。

示例 1: 排序算法 - 快速排序扩展

我们将添加一个方法来检查数组是否已经排序，以及一个主函数来测试排序算法。

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

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

    public static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println("\nIs sorted? " + isSorted(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

示例 2: 查找算法 - 二分查找扩展

我们将添加边界检查和异常处理，以确保数组不为空且是有序的。

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) throws IllegalArgumentException {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("Array is empty or null.");
        }
        if (!isSorted(arr)) {
            throw new IllegalArgumentException("Array must be sorted.");
        }
        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;
    }

    private static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 5;
        try {
            int index = binarySearch(arr, target);
            System.out.println("Element found at index: " + index);
        } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

示例 3: 动态规划 - 斐波那契数列扩展

我们将添加一个方法来计算斐波那契数列的所有项，并添加一个主函数来展示结果。

public class FibonacciDP {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static int[] fibonacciSequence(int n) {
        int[] sequence = new int[n];
        for (int i = 0; i < n; i++) {
            sequence[i] = fibonacci(i);
        }
        return sequence;
    }

    public static void main(String[] args) {
        int n = 10;
        int[] sequence = fibonacciSequence(n);
        System.out.println("Fibonacci sequence up to " + n + ":");
        for (int num : sequence) {
            System.out.print(num + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

通过这些扩展，我们不仅增强了代码的功能性，还增加了异常处理和验证，使得代码更加健壮和实用。在实际开发中，这些额外的考虑对于确保程序的稳定性和正确性是非常重要的。