Оцените порядок роста алгоритма из времени выполнения и отношения изменения

Question

Я начинаю практиковать с алгоритмами. Ниже список представляет собой алгоритм, который я запускал, и записывал время и соотношение изменений. Я не уверен, как определить порядок роста из этого списка. Какие факторы я должен учитывать? Я очень благодарен за объяснительный ответ.

N |seconds | ratio | log(base of 2) ratio 
--------------------------------------- 
512 0.12 4.14  2.05 
1024 0.49 4.24  2.08 
2048 2.08 4.24  2.08 
4096 8.83 4.24  2.08 

Answer 1

Сравните время для вашего маленького вклада в различных больших входы:

• оГО увеличение N (512-> 1024) приводит к увеличению 4x в время работы.
• 4-кратное увеличение N (512-> 2048) приводит к увеличению времени работы на 16 раз.
• Увеличение в 8 раз в N (512-> 4096) приводит к увеличению времени работы на 64 раза.

Исходя из этого, можно экстраполировать, что к й увеличение N приведет к к й увеличения времени работы, что указует на O (п) алгоритм.