Текущая сложность:
Давайте назовем 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) и не можем быть лучше, поскольку нам нужно прочитать каждое число.Так что это оптимально