Вычислительный алгоритм Runtime?

Question

Это скорее вопрос CS, но, надеюсь, кто-то может мне помочь. Если конкретный алгоритм имеет время выполнения T (100) = 20, как я могу оценить время выполнения заданного T (400), a) T (n) = O (n) или b) T (n) = O (n^2)? Для a я решил, что если 100 элементов занимают 20 единиц (пространства или времени), то линейно 400 элементов занимают около 80 единиц. Правильно ли такое мышление? Если да, то как можно подойти b)? Если нет, то каков правильный способ вычислить это? Благодаря !

Answer 1

Сделав еще несколько предположений, как п достаточно велико, что вы действительно видите асимптотическое поведение и алгоритмы Omega (п) и Омега (п^2), соответственно, вы действуйте следующим образом:

а) Т (n) = c * n; учитывая, что T (100) = 20, находим c = 0,2 и T (400) = 80

b) T (n) = c * n^2; T (100) = 20 -> c = 0,002; T (400) = 320