分析算法 最佳、最坏和平均情况

Question

我想知道 find 和 replaceAll 方法的最佳、最差和平均情况以及增长函数，它基本上是在以下代码中数组大小大于零的每种情况下执行的语句数/** * Return index where value is found in array or -1 if not found. * @param array ints where value may be found * @param value int that may be in array * @return index where value is found or -1 if not found */public static int find(int[] array, int value) {    for (int i = 0; i < array.length; i++) {        if (array[i] == value) {            return i;        }    }    return -1;}/** * Replace all occurrences of oldValue with newValue in array. * @param array ints where oldValue may be found * @param oldValue value to replace * @param newValue new value */public static void replaceAll(int[] array, int oldValue, int newValue) {    int index = find(array, oldValue);    while (index > -1) {        array[index] = newValue;        index = find(array, oldValue);    }}

Answer 1

这是用于 find(...) 方法的

你很容易知道最好和最坏的情况：

最好的情况是您要搜索的元素是数组中的第一个元素。在这种情况下，只需 1 次迭代即可找到您的元素，即O(1)恒定时间。

同样，最坏的情况是当您要搜索的元素在数组中不存在时，因此您遍历整个数组却一无所获。在这种情况下，它需要 n 次迭代（其中 n 是数组的大小），O(n)线性时间。

大多数情况下，最坏的情况很容易确定。您可以简单地查看嵌套循环。如果您有x大量嵌套循环，其中所有循环都以线性时间在数组上迭代，那么您的时间复杂度为 O(n^x)。因此，在 replaceAll(...) 中，您有 2 个嵌套循环（while并且for来自您的find(...)方法），这意味着复杂性是O(n^2)最坏的情况replaceAll(...)

对于一般情况：

find(...)我为你的函数写了一个测试：

public static void main(String[] args) {

    int iterationsTotal = 0;

    int timesTested = 100000;

    //Test 1000 times

    for(int i = 0; i < timesTested; i++) {

        int n = 100; //Array size to test 

        int[] array = new int[n];

        //Populate the array

        int j = 0;

        for(j = 0; j < array.length; j++) {

            array[j] = (int)(Math.random() * 100);

        }

        //You can search for any number, even 99. It will always result in 25 average.

        iterationsTotal += find(array, 5);

    }

    System.out.println(iterationsTotal / timesTested);

}

上面的代码测试了你的 find 函数 100,000 次。它计算它所花费的平均迭代次数，每次我运行它时，它通常会达到约 25 次。使用大小为 100 的数组，平均 25 次迭代来找到您正在搜索的元素。这就是O(n/4)n = 数组的大小，在本例中为 100。这与 O(n) 一样好（为什么要忽略计算算法运行时间复杂度的常数）。find(...)因此，您的算法的平均情况为 O(n) 。你可以为replaceAll(...)

Answer 2

寻找

• 充其量我们在第一个位置找到所需的序列，所以：Ω(1)

• 在最坏的情况下，我们最后找到了所需的序列，所以：O(n)

• 平均值：Θ(n )

全部替换

• 这将是最坏的O(n^2)因为它需要搜索所有字符以找到所需的替换。

成长功能？

• 上面的代码中没有任何增长方法，所以我将为您提供复制数组的时间复杂度。所有情况都是线性的O(n)。

我希望这可以帮到你。

Answer 3

您的运行时在O(n^2)

• 最佳情况：该数组恰好包含一项与您要替换的值相等的项。此项目也是数组中的第一项。在n迭代中运行

• 最坏情况：数组中的所有项目都等于您要替换的值。这将在n^2迭代中运行

一个简单的优化，使它在O(n)

如果你想进入O(n)，你需要在使用时传递起始索引，find这样你就不必从数组的开头重复搜索

public static int find(int[] array, int value, int start) {

    for (int i = start; i < array.length; i++) {

        if (array[i] == value) {

            return i;

        }

    }

    return -1;

}

public static void replaceAll(int[] array, int oldValue, int newValue) {

    int index = find(array, oldValue);

    while (index > -1) {

        array[index] = newValue;

        index = find(array, oldValue, index);

    }

}