Sqrt (n) сложность времени

Question

Я новичок во времени и асимптотических обозначениях. Я смотрел это видео: https://www.youtube.com/watch?v=9TlHvipP5yA, чтобы выяснить временную сложность кода, показанного ниже

Код приходит к выводу, что сложность времени для кода ниже составляет O (Sqrt (n));

Когда я предоставляю разные значения n, я ожидаю Sqrt (n) # выходов, но это не подтверждает анализ O (Sqrt (n)). Может кто-нибудь объяснить, почему это так?

Например, если у меня n = 10, я ожидаю Sqrt (10) выходов, что составляет ~ 3 выхода или 4, если вы округлите, я думаю. Это нелогично?

Заранее спасибо.

p = 0;
for( int i = 0; p <= n; i++){
  p = p + i;
  System.out.println(p);
}

Answer 1

Big O не используется для вычисления количества инструкций, которые вы ожидаете выполнить.Для заданного n вычисление квадратного корня из n не даст вам точного числа выполнений инструкции.Big O описывает, что происходит с вашей функцией , так как размер ввода становится очень большим .Анализ вашей функции, когда n равно 10 или даже 100, не относится к Big O.

Когда мы говорим, что временная сложность функции равна O (sqrt (n)), мы имеем в виду, что функция принадлежит к классуфункции, где требуемое время пропорционально квадратному корню из значения n, , но только для очень больших значений n .

Если вы смотрите видео, инструктор упрощает термин k (k + 1) / 2 до k ^ 2, принимая начальный член, поскольку термин k становится незначительным по сравнению с термином k ^ 2, , когда k очень большое .