Как вычислить временную сложность бесконечного цикла, который обязательно закончится в точке? - PullRequest
Новая
       30

Как вычислить временную сложность бесконечного цикла, который обязательно закончится в точке?

0 голосов
/ 14 мая 2019

Итак, у меня есть следующий код, для которого я сначала использовал while(true) с разрывом, используя оператор if с тем же условием, которое сейчас находится в моем цикле do-while.

Код теперь выглядит так: 

do {
        for (int i = 0; i < arrayToUse.length; i++) {
            int diff = arrayToUse[i] - number;

            if (diff >= 5) {
                arrayToUse[i] -= 5;
                count++;
                break;
            }

            if (diff >= 2) {
                arrayToUse[i] -= 2;
                count++;
                break;
            }

            if (diff == 1) {
                arrayToUse[i] -= 1;
                count++;
                break;
            }
        }

        if(preCount == count)
            break;

        preCount = count;

    } while (!allElementsEqual(arrayToUse, number));

Здесь arrayToUse - массив, который я получаю в качестве ввода. И код для allElementsEqual() выглядит так: 

static boolean allElementsEqual(int[] arr, int num){

    for(int i=0;i<arr.length;i++){
        if(arr[i] != num)
            return false;
    }

    return true;
}

У меня есть тайм-ауты в коде, для которого я его использую, и я не могу найти, как я могу вычислить временную сложность алгоритма, который не имеет точно определенного времени окончания. Я говорю о сложности времени в Big Oh Notation.

Буду признателен за любую помощь.

Ответы [ 2 ]

2 голосов
/ 14 мая 2019

Текущая сложность:

Давайте назовем m максимальный номер массива.Ваш первый цикл будет выполняться не более N раз, чтобы найти число, которое все еще больше, чем num.Когда это происходит, это приближает его к количеству максимум в 5 единицах.Единицы 2 и 1 не важны для сложности, но важная часть заключается в том, что они всегда будут приближать его к num.

Поэтому, когда вы изменили элемент, вы нарушаете цикл, чтобы найти число итогда не будет нарушать сделку, поскольку предварительный отсчет будет отличаться от счета.Затем запускается функция allElementsEqual, и это тоже O (n).Таким образом, для каждого запуска do while вы выполняете дважды O (n) операций.Остается только то, сколько раз это можно сделать во время выполнения цикла.

Он может остановиться только тогда, когда все элементы равны, и мы сказали, что на каждом шаге мы приближаем 1 число к нулю максимум на 5. Это будетозначает, что для каждого числа в нашем массиве оно будет выполняться примерно ((originalNumber [i] - num) / 5) раз, а наихудший случай - это максимум, равный m.Таким образом, потребуется около (m - num) / 5 циклов, чтобы привести только это число, равное num.Если бы все числа были максимальными, это означало бы, что для каждого числа мы будем делать (m - num) / 5 шагов, чтобы сделать его равным num.

Это дает нам (m - num) / 5 шагов для каждогочисло, есть N чисел, и каждый шаг стоит O (n), что в целом дает сложность O ((m - num) / 5 * N * N).Мы можем удалить / 5 и просто оставить его как O ((m - num) * N * N).

В качестве примечания, используя while (true) вместо allElementsEqual, то же самое, потому что ваш предсчет== считать, если уже позаботился о проверке этого.

Можем ли мы добиться большего успеха?

Предполагая, что мы удаляем allElementsEqual для true, это меняет операцию на O1) вместо O (n), но у нас все еще есть цикл, чтобы найти число, не равное num, то есть O (n).Если мы изменим i для инициализации в 0 за пределами do while, чтобы он не начинался с 0 на каждом шаге, он изменит операцию на O (1) и все еще будет работать, потому что разрывы будут препятствовать обновлению i до тех пор, покаразница равна 0, а когда разница равна 0, мы больше не заботимся об этом числе, поэтому можем увеличить i.Это меняет алгоритм на O ((m - n) * N)

Можем ли мы сделать еще лучше?

Вместо того, чтобы приблизить число к num с максимум5 единиц, почему бы нам не сделать все это сразу?Мы можем посчитать, сколько раз нам понадобится уменьшить его на 5, сколько раз мы уменьшим в 2 (0, 1 или 2 раза), а сколько раз - в 1 (0 или 1 раз). 

int diff = arrayToUse[i] - number;

count += floor(diff / 5) + floor((diff % 5) / 2) + (diff % 5) % 2
arrayToUse[i] = number;

С этим мы можем сделать это в O (N) и не можем быть лучше, поскольку нам нужно прочитать каждое число.Так что это оптимально

0 голосов
/ 14 мая 2019

Я бы сказал O(n² + n*m), где n - это длина arrayToUse и m максимального значения, содержащегося в массиве.

В худшем случае вам придется запускать основной цикл n раз, чтобы изменить каждый элемент и установить его равным num, так как каждый запуск может обновлять один элемент за раз. Таким образом, у нас есть внешний n коэффициент умножения.

Тогда у нас есть стоимость каждого цикла, которая, кажется, равна O(n + m), поскольку O(n) - это стоимость теста, а O(m) - это стоимость обновления каждого элемента, чтобы уменьшить его до num.

Итак O(n² + n*m).

...