Алгоритм банкира вычислил временную сложность
Существует много возможных ловушек для записи микросравнительных тестов в Java.
Сначала: необходимо вычислить со всеми видами событий, которые занимают время более или менее случайные: Сборка "мусора", кэшируя эффекты (ОС для файлов и ЦП для памяти), IO и т.д.
112-секундный: Вы не можете доверять точности измеренных времен для очень коротких интервалов.
Треть: JVM оптимизирует Ваш код при выполнении. Таким образом, различные выполнения в том же экземпляре JVM станут быстрее и быстрее.
Мои рекомендации: Сделайте свой контрольный прогон несколькими секундами, который более надежен, чем время выполнения по миллисекундам. Нагрейтесь JVM (означает выполнять сравнительный тест, по крайней мере, однажды без измерения, что JVM может выполнить оптимизацию). И выполненный Ваш сравнительный тест многократно (возможно, 5 раз) и берут среднее значение. Работайте каждый микросравнительный тест в новом экземпляре JVM (призовите к каждому сравнительному тесту новый Java), иначе, эффекты оптимизации JVM могут влиять позже на запускающие тесты. Не выполняйте вещи, которые не выполняются в фазе прогрева (поскольку это могло инициировать загрузку класса и перекомпиляцию).
1 ответ
В приведенной ниже части представлена временная сложность (n * m)
for I = 1 to N do // *n times
if ((not FINISH[i]) and
NEEDi <= WORK) then // *m times, if it's an array search
, но она также вложена в цикл repeat . Если этот цикл может выполняться, в худшем случае, n раз, то процедура имеет временную сложность O (n * n * m).
Обновление: Я кое-что пропустил,
WORK = WORK + ALLOCATION_i; // also O(m) operation, vectors addition
Итак, код, который выполняется в цикл for имеет временную сложность O (m + m).
Конечно, O (m + m) = O (m), и конечная сложность составляет O (n * n * m).