Как оценить сложность среднего случая с учетом размера ввода и среднего времени? - PullRequest
0 голосов
/ 08 февраля 2020

Я пытаюсь определить среднюю временную сложность программы. Мне удалось найти время завершения для определенных входных размеров, таких как:

Размер-Время

12 - 0,11552862

13 - 0,12365744

14 - 0,20763664

15 - 0,51893218

16 - 1,66423617

17 - 7,625521

И я создал график. График

Можно ли найти сложность времени только с помощью этой информации. Я сейчас немного потерян.

1 Ответ

0 голосов
/ 08 февраля 2020

Нет, невозможно найти сложность времени только с помощью этой информации. Без рассмотрения кода определение сложности времени в этом случае невозможно.

Один (из многих) простых примеров, когда этот анализ времени и входных данных не подходит, если у вас есть определенные операторы if в вашем коде, которые вызывают выполнение чего-то, что предоставленные вами входные данные не учитывают.

Вы можете сослаться на этот ответ:

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

Другой полезный ответ:

Big O, как вы рассчитываете / приближаете его?

...