Алгоритм анализа Лучший, Худший и Средний случай - PullRequest
Новая
       10

Алгоритм анализа Лучший, Худший и Средний случай

0 голосов
/ 13 февраля 2019

Я хочу знать, каков наилучший, наихудший и средний случай для методов 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);
    }
}

Ответы [ 3 ]

0 голосов
/ 13 февраля 2019

Найти

  • В лучшем случае мы находим желаемую последовательность в первом месте так: Ω (1)
  • В худшем случаемы находим желаемую последовательность последней так: O (n)
  • Среднее : Θ (n)

ReplaceAll

  • В худшем случае это будет O (n ^ 2) , потому что для поиска нужных замен ему необходимо найти все символы.

Функция роста?

  • В приведенном выше коде не было никакого метода роста, поэтому я предоставлю вам временную сложность для копирования массива. Все случаи являются линейными O (n) .

Надеюсь, это было полезно.

0 голосов
/ 13 февраля 2019

Время выполнения: 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);
    }
}
0 голосов
/ 13 февраля 2019

Это для метода 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);

}

Приведенный выше код проверяет вашу функцию поиска 100 000 раз.Он вычисляет среднее количество итераций, которое он принял, и обычно составляет ~ 25 каждый раз, когда я его запускаю.Используя массив размером 100, в среднем 25 итераций, чтобы найти элемент, который вы ищете.Это приходит к O(n/4), где n = размер массива, в данном случае 100. Это так же хорошо, как O (n) ( Зачем игнорировать константы при вычислении сложности времени выполнения алгоритма ).Таким образом, средний случай будет O (n) для вашего find(...) алгоритма.Вы можете сделать то же самое для replaceAll(...)

...