Является ли временная сложность этого метода постоянной?
Мне было поручено определить временную сложность этого метода, но я не уверен, почему она постоянна.
Я думал, что общая временная сложность равна n2^n, потому что внешний цикл выполняется n раз, а внутренний цикл выполняется 2^k раз, потому что k умножается на коэффициент два при каждом запуске внешнего цикла. Однако, когда я тестировал метод с помощью System.nanoTime(), время, похоже, оставалось постоянным при увеличении размера данных. Я не уверен, прав я или нет, но если я ошибаюсь и метод имеет постоянную временную сложность, не могли бы вы объяснить, почему? Спасибо!
public static void f6(int n) {
int k = 1, a = 0;
for(int i = 0; i < n; i += 1) {
for(int j = 0; j <= k * 2; j += 1) {
a = i + j;
}
k = k * 2;
}
}
Тестовый левый столбец: имя функции; средний столбец: количество предметов; правая колонка: затраченное время:
Возможно, стоит посмотреть, что оптимизатор сделал с этим кодом. Поскольку возвращаемого значения нет, возможно, все это было заменено возвратом. Сделайте это int f6(int n) и измените внутренний цикл на a += i+j. В противном случае есть компиляторы, которые заметят, что a = i + 2^i при выходе из внутреннего цикла и в последний раз через цикл i=n-1. IOW они придут к выводу, что возврат n-1+k^(n-1) может быть вычислен за постоянное время, и внешний пользователь никогда не заметит разницы. Попробуйте синхронизировать его в режиме отладки, когда он выполняет код дословно, и вы можете получить более содержательные ответы.
Возможно, вас это заинтересует: stackoverflow.com/questions/504103/…
@MartinBrown Оптимизаторы также, вероятно, смогут определить, что a всегда пишется, а не читается, а это означает, что его можно удалить; что оставляет внутренний цикл пустым, поэтому его можно удалить.
Если не компилятор, то среда выполнения также выполняет оптимизацию, если вы запускаете ее повторно и замечает это.
@yshavit на самых агрессивных оптимизирующих компиляторах высшего класса сегодня вы должны, по крайней мере, распечатать возвращаемый результат тестируемой функции или сделать с ней что-то еще, что имеет побочные эффекты, чтобы быть уверенным, что она выполняется при полной глобальной оптимизации. Я обычно использую if (result ==42) printf("Surprise\n"); для этой цели. До сих пор ни один оптимизатор не разглядел этот обман.
@MartinBrown Конечно, но внутренний цикл ничего не печатает и не имеет каких-либо других очевидных побочных эффектов. И я предполагаю, что оптимизатор может это понять.
О, вообще-то, извини, ты просто предложил обходной путь к тому, что я сказал?
Ответы 3
Вы определили переменные a и k как целые числа и (по крайней мере, переменную k) нельзя увеличить до ^2 более 32 раз. Таким образом, JVM «знает», что уравнение k = k^2 имеет смысл только первый 31 раз и не будет выполнять чрезмерных итераций.
Более того, если вы не используете результат после расчета, JVM также может решить не выполнять расчет.
Итак, решение:
- замените
int a,kнаlong a,k(учтите, что теперь функция имеет смысл только при n <= 64). - Использовать результат (sysout будет достаточно)
Я думал, что общая временная сложность равна n2^n, потому что внешний цикл выполняется n раз, а внутренний цикл выполняется 2^k раз, потому что k умножается на коэффициент два при каждом запуске внешнего цикла.
Что ж, O(n2n), безусловно, является верхней границей асимптотической сложности метода. Ваш анализ верен, насколько это возможно. Но если вы посмотрите немного глубже, вы можете получить более плотный вариант, который по-прежнему имеет простую форму.
Запишите некоторые счетчики итераций внутреннего цикла:
1 2 4 8 ...
вплоть до 2n-1. Сумма всех этих чисел может быть выражена как Σi = 1…n 2i-1. Если вы еще не знаете результат этой суммы, то вам следует это выучить. И я позволю тебе это сделать.
Однако, когда я тестировал метод с помощью
System.nanoTime(), время, похоже, оставалось постоянным при увеличении размера данных.
Бенчмаркинг гораздо сложнее, чем может показаться. Есть несколько причин, по которым наивный тест, такой как вы описываете, может быть неточным. Оптимизация компилятора, поведение JIT, загрузка машины и даже некоторая степень случайных колебаний — все это может сыграть против вас, по крайней мере, в отношении оценки асимптотической сложности через время выполнения.
Предположим, например, что достаточно умный компилятор может понять, что весь метод можно свести к нескольким операциям (на самом деле константным) и выдать код, который просто делает это вместо фактического выполнения циклов. Я не думаю, что ваш компилятор достаточно умен для этого, но теоретически это возможно.
Будет ли сумма равна 2^n-1? В таком случае, почему это будет более жесткая граница, если ее можно упростить до 2^n?
@WoojinRho, 1 * (2^n) - 1 — более жесткая граница, чем ваша n * (2^n), потому что коэффициент 1 в первом асимптотически меньше, чем соответствующий коэффициент n во втором. Однако было бы общепринято игнорировать - 1 и просто писать его как O(2^n) (а не как предложенный вами O(n2^n)). Возможно, вы не понимаете, что это охватывает все операции во всем гнезде циклов, а не только во внутреннем цикле.
Если вы посмотрите на значения k (который определяет, как часто выполняется внутренний цикл), вы найдете следующие значения:
1 2 4 8 ... 536870912 1073741824 -2147483648 0 0 0
Количество запусков внутреннего цикла ограничено и для достаточно больших значений n (при n = 31). После этого время выполнения этого метода увеличивается только линейно со значением n (поскольку внешний цикл по-прежнему выполняется от 32 до n).
Таким образом, для значений n от 1 до 31 он работает за O(2^n), для больших значений — за O(n).
Конечно, это не постоянно. Проблема в том, что измерение времени, которое занимает тот или иной код, гораздо сложнее, чем простое использование nanoTime. используйте JMH и убедитесь, что время тестирования достаточно велико.