s=0; c=n; p=log(n);
for (h=1; h<p; h++) {
c = c/2;
for (j=1; j<c; j++) {
for (k=1; k<=h; k++)
s++;
}
}
Какова временная сложность в следующем фрагменте кода, где п представляет собой целое положительное число:Какова временная сложность в следующем фрагменте кода, где п представляет собой целое положительное число:
Использование Sigma нотации, вы можете получить точное число итераций (Предполагается, что журнал имеет основание 2):
вы можете вывести на порядок роста, а также (Наглядно линейный, но вы можете это доказать с помощью пределы):
Я не думаю, что OP может понять это. Возможно, вы можете использовать эту теорию и примениться к его конкретному примеру? (Если применимо) – dfri
Это применяется к конкретному примеру. Можно проследить индексы * h *, * j * и * k *. Остальное является неосуществимым (например, * c * есть * n/2^k *, но изменение * c * не ясно, если оно хранится как в самом алгоритме). –
Ах, извините, мое плохое, вы правы. Благодаря! – dfri
ли журнал (п) основание 2 или любой? –