Как рассчитать сложность времени и пространства алгоритмов

Question

Как вычислить пространственную и временную сложность алгоритмов в java.

Общее время выполнения [Using System.nanoTime()] равна временной сложности любого алгоритма или функции?

Пример: оценка пространства и времени Сложность энного количества в серии Фибоначчи

Answer 1

Сложность времени является теоретическим признаком масштабируемости на идеализированной машине. (его об алгоритме, а не о машине)

System.nanoTime() расскажет вам, как долго что-то заняло конкретный компьютер в определенном состоянии для конкретных входов данных.

Сложность времени лучше для разработки наихудших значений, измерение более полезно, если у вас есть конкретный вариант использования, который вы хотите рассмотреть.

Answer 2

Сложность алгоритма не имеет абсолютно ничего общего с временем, которое требуется, чтобы запустить его в вашей системе, в текущем контексте. Вы можете получить его в результате математического изучения алгоритма, ни один тест не выполнит.

Однако вы можете иметь эмпирическое приближение, если вы запустите его, скажем, 500 раз с разными записями, скопируйте результаты, а затем найдите подходящую кривую.

И это все, что вы получаете. Пойдите учиться, человек.

Answer 3

Общее время выполнения [Использование System.nanoTime()] равно сложности по времени любого алографита или функции?

Количество При расчете порядка сложности программы, это обычно делается в Большой-O нотации. Here - это все, что вам нужно знать об этом. С примерами.

Answer 4

Во-первых, вы должны определить основную работу алгоритма. Поместите счетчик, чтобы рассчитать, сколько раз основная операция работает, пока ваш алгоритм не завершит работу. Попробуйте обозначить этот счетчик как n. В серии fibonacci основная операция - добавление (добавление последних двух элементов дает вам следующий) Для вычисления n-го числа необходимо добавить n-1. Таким образом, сложность ряда фибоначчи реализуется как O (n)