Расчет большой тета из Runtime?

Question

У меня есть программа, которая вычисляет время выполнения в миллисекундах из 4 файлов .txt. Затем я должен вычислить, что время загрузки загружается в терминах theta, и указать, что n указывает на вход. Однако я до сих пор не совсем понимаю большую тета-нотацию или асимптотическую нотацию, если на то пошло. Может ли кто-нибудь дать мне несколько указателей? Это были автономной работы для файлов: Время

Файл для загрузки

file1 18000ms

file2 48514ms

file3 121473ms

file4 622446ms

Answer 1

Там нет общего способа вывести тета-привязку во время выполнения программы из ее эмпирической среды выполнения. Могут быть данные, которые вы не видели, что триггер патологических наихудших случаев (например, симплекс-алгоритм для линейного программирования ухудшается до экспоненциального наихудшего времени на узком классе входов), и у вас нет способа узнать, будут ли ваши тенденции «Наблюдение продолжается дольше.

Если вы хотите вычислить сложную вычислительную сложность, разумным решением будет взятие ваших данных, построение графика на оси журнала и журнала и поиск оптимальной линии. Причина этого заключается в том, что прямая линия на логарифмическом/логарифмическом графике соответствует полиномиальной подгонке, так что это найдет лучший подходящий полином для данных, которые у вас есть. До тех пор, пока вы помните, что ваш ответ будет только таким же хорошим, как данные, которые вы предоставляете, это отличный способ оценить сложность.