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

Question

Для моего экзамена по программированию и разработке алгоритмов мне нужно знать временную сложность и нотацию Big-Oh. Я понимаю большую часть этого, но потом я столкнулся с этим вопросом, и решение, которое я имею, кажется довольно простым; но я не понимаю, какие шаги необходимы. Может ли кто-нибудь прояснить, что предприняли шаги?

Упражнение:

Квадратичной алгоритм с временем обработки Т (п) = сп^2 проводит Т (N) секунд для обработки N элементов данных. Сколько времени будет потрачено на обработку n = 3000 элементов данных, если предположить, что N = 100 и T (N) = 1 мс?

Учитывая решение:

Постоянный множитель с = Т (N)/(N^2), поэтому Т (п) = Т (N) * (п^2)/(N^2) = n^2/10000 и T (3000) = 900 мс

Answer 1

Это довольно простая математика проблема:

Если T(n) = cn² и T(100) = 1ms затем

T(100) = c * 100² 
     = c * 10,000 
     = 1ms 

Поэтому решение для c дает:

c = (1/10,000)ms 

Это может быть использован для вычислить T(3000):

T(3000) = (1/10,000)ms * 3,000² 
     = (1/10,000)ms * 9,000,000 
     = (9,000,000/10,000)ms 
     = 900ms 

Answer 2

Это прямолинейно. У вас есть N = 100, T(N) = 1. Итак, c = T(N)/N^2 = 1/10000.

Тогда вы делаете T(3000) = 1/10000 * (3000^2) = 900.

Answer 3

Это не имеет ничего общего с нотами Big-Oh или даже с информатикой. Все, что вам нужно, это базовая алгебра. Учитывая, что T (n) = cn^2 для некоторого c, а T (100) = 0,001, что такое T (3000)?

0.001 = T(100) = c (100*100) = 10000c 
    c = 10^-7 

    T(3000) = c n^2 = 10^-7 * 3000 * 3000 = 0.9