Как рассчитать временную и пространственную сложность алгоритмов
Как рассчитать пространственную и временную сложность алгоритмов в Java.
Общее время выполнения [ Using System.nanoTime() ] равно временной сложности любого алогрита или функции?
Пример: оценка сложности пространства и времени n-го числа в рядах Фибоначчи
4 ответа
Временная сложность является теоретическим показателем масштабируемости на идеализированной машине. (о алгоритме, а не о машине)
System.nanoTime () скажет вам, сколько времени заняло что-то на конкретной машине, в определенном состоянии для конкретных вводов данных.
Сложность по времени лучше для определения наихудших значений, измерение более полезно, если у вас есть конкретный вариант использования, который вы хотите рассмотреть.
Общее время выполнения [ Using System.nanoTime() ] равно временной сложности любого алогрита или функции?
Нет. При расчете порядка сложности программы это обычно делается в формате Big-O. Вот все, что вам нужно знать об этом. С примерами.
Сложность алгоритма не имеет абсолютно никакого отношения к времени, которое требуется для его запуска в вашей системе, в вашем текущем контексте. Вы можете получить его в результате математического изучения алгоритма, никакой тест не подойдет.
Однако вы можете получить эмпирическое приближение, если, например, выполнить его 500 раз с разными записями, составить таблицу результатов, а затем найти подходящую кривую.
И это все, что вы получаете. Иди учись, чувак.
Во-первых, вы должны определить основные операции алгоритма. Поставьте счетчик, чтобы вычислить, сколько раз базовая операция работает, пока ваш алгоритм не завершит работу. Попробуйте обозначить этот счетчик как n. В серии Фибоначчи основной операцией является сложение (добавление двух последних элементов дает следующее). Для вычисления n-го числа необходимо выполнить n-1 сложение. Итак, сложность рядов Фибоначчи реализуется как O(n)