Какова сложность ниже программы:времени Сложность расчета алгоритма
void function(int n)
{
int i, j, k , count =0;
for(i=n/2; i<=n; i++)
for(j=1; j=j + n/2<=n; j++)
for(k=1; k<=n; k= k * 2)
count++;
}
Теперь, как в моем понимании внешний цикл выполняется п/2 раз. Внутренний цикл выполняется n/2 раза, а третий внутренний цикл выполняет журнал n раз. Теперь, если обозначить временную сложность алгоритма как функцию T (n).
Т (п) = п/2 * п/2 * войти п = п^2/4 * войти п
Теперь для очень больших размеров входного п Термин журнал п становится слишком малым по сравнению с термом n^2. Поэтому при моем понимании временная сложность алгоритма должна быть O (n^2). Но я проверил ответ этой вышепрограммной программы, он говорит, что ответ O (n^2logn).
Может ли кто-нибудь помочь мне понять, почему мы не можем игнорировать термин log n для больших значений n? Или расчет, сделанный мной неправильно?
Да, журнал (п) меньше, чем полином, но когда он умножается это еще фактор. O (log (n)) медленнее, чем O (n), но O (nlogn) - вещь, и она похожа на то, что у вас есть. O (nlogn)! = O (n). График может иллюстрировать эту скважину. – keyser
Спасибо ключи. Скажем, например, если у нас есть временная сложность T (n) = n^3 + n^2 + n, то при очень больших значениях n мы игнорируем член n^2 и n, тогда почему мы не можем сделать то же самое здесь ? – Beast
Да, мы делаем, потому что они разделены. Асимптотически другие не будут иметь никакого заметного воздействия, но асимптотически O (nlogn) растет быстрее, чем O (n), так как log (n) больше константы. Мне понравилась иллюстрация бенджи о том, как они удалены. – keyser