Sqrt(n) временная сложность
Я новичок во временных сложностях и асимптотических обозначениях. Я смотрел это видео: https://thewikihow.com/video_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);
}
Я не понимаю, что вы спрашиваете. В чем именно заключается ваш вопрос?
Big O описывает асимптотическое поведение (с точностью до умножения на константу) при больших значениях n. Вы не можете вывести из этого время для n = 10.
Итак, неправильно предполагать, что если у меня n = 100, у меня будут операторы root(100) System.out.print?
Нет. Если 100 достаточно велико, чтобы демонстрировать асимптотическое поведение, вы получите отпечатки c*sqrt(100) для некоторой константы c.
Можете ли вы объяснить, что вы имели в виду под этим - Big O описывает асимптотическое поведение (с точностью до умножения на константу) для больших значений n.????
Возможный дубликат Большой О, как вы рассчитываете/аппроксимируете это?
Ответы 1
Большой 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 очень велико.
Спасибо за объяснение
Извините за ошибку. Я исправил код.