算法的运行时间优化

Question

我正在尝试找到一种方法来优化我的算法，使运行时间为 O(n²)（大 O 表示法）。

输入是一个有n个元素的数组，只有正整数和负整数。我们可以假设数组已经排序。

我要确定：对于每个r（数组的元素），是否r = s + t，其中s和t也是数组的元素，并且可以相同（s == t），或者也为零。

我试图通过检查当前数字是正数还是负数来减少我必须检查的元素数量，但是运行时间仍然太长。问题是我使用了 3 个 while 循环，这意味着最坏情况下的运行时间为 O(n³)。

这是我的代码：

public static void Checker(int[] array) {
    List<Integer> testlist = new ArrayList<Integer>();
    int i = 0;
    while (i < array.length) {
        int current = array[i];
        if (attached(current, array)) {
            testlist.add(current);
        }
        i++;
    }
}

public static boolean attached(int current, int[] array) {
    boolean result = false;
    int i = 0;
    while (i < array.length && !result) {
        int number1 = array[i];
        int j = 0;
        while (j < array.length && !result) {
            int number2 = array[j];
            if (number1 + number2 == current) {
                result = true;
            }
            j++;
        }
        i++;
    }
    return result;
}

Answer 1

计算s+t所有可能的和并将结果放入一个集合=> O(n²)
遍历每个 r 并检查是否有一个总和与 r => O(n) 相匹配，因为 set.contains 在恒定时间内运行。

Answer 2

您可以开始对数组 O(nlogn) 进行排序（如果没有），然后对于数组中的每个元素，您可以检查是否有两个元素的总和等于 O(n²) 中的数字.

代码在C#:

public static bool Solve(int[] arr)
{
    Array.Sort(arr);    //If not already sorted

    foreach (var num in arr)
        if (!FindTwoThatSumN(arr, num))
            return false;

    return true;
}

public static bool FindTwoThatSumN(int[] arr, int num)
{
    int min = 0;
    int max = arr.Length - 1;

    while (true)
    {
        if (min == max) break;

        int sum = arr[min] + arr[max];

        if (sum < num) min++;
        if (sum > num) max--;
        if (sum == num) return true;
    }

    return false;
}

检查数组中是否有两个数字（必须排序）求和特定值的想法是从最小值 (min = 0) 和最大值 (max = arr.Length) 开始，然后在每次迭代中：

如果总和小于数字，增加min索引。
如果总和大于数字，减少max索引。
如果总和等于数字，那么你就找到了解决方案。
如果min索引达到max则无解

你可以参考这篇question/answers了解更多细节和证明。

整体解决方案的时间复杂度为O(n²):

对数组进行排序：O(nlogn).
迭代排序数组：O(n).
求出两个相加值的数字：O(n)。

因此，O(n²) 是由于对 FindTwoThatSumN 的嵌套调用。

如果您愿意，可以将索引而不是数字传递给 FindTwoThatSumN 方法，以避免使用数字本身作为解决方案的一部分进行额外检查。

算法的运行时间优化

Algorithm's Running Time Optimization

algorithm

optimization

time

big-o

while-loop

算法的 运行 时间优化

Algorithm's Running Time Optimization

algorithm

optimization

time

big-o

while-loop

算法的运行时间优化