Какова сложность Big O постоянно уменьшающегося диапазона в цикле for?

У меня получилось 2 вложенных for цикла, я вычисляю новое значение для nrResults при каждом выполнении внутреннего for цикла (который будет зацикливаться nnrResults - 2 раза).

Временная сложность должна быть порядка O(n), так как nrResults зависит от значения n.
Но nrResults уменьшается на каждом цикле внешнего цикла for (т.е. firstNext * j растет с каждой итерацией)

Является ли временная сложность внутреннего цикла for все еще O(n), хотя nrResults будет продолжать уменьшаться на протяжении всего выполнения?

for(int j = 1; j < B; j++)                      // General case
{
    nrResults = n - (firstNext * j);
    result = codedInput[0] + results[minI = minIndex(results, 0 + firstNext, nrResults + firstNext)];
    
    for(int i = 1; i < nrResults; i++)
    {
        if ( (i + firstNext) > minI)
            results[i] = codedInput[i] + results[minI = minIndex(results, i + firstNext, nrResults + firstNext)];
        else
            results[i] = codedInput[i] + results[minI];

        if (results[i] < result)
            result = results[i];
    }
}

Внутренний цикл выполняется nResults - 1 раз, а поскольку nResults < n, он выполняется не более n раз, то есть O(n). Помните, что нотация большого O не является жесткой границей. Это также O(n^2). Общая сложность — это просто математика. сумма (n - j * firstNext для j = 1..B). Отвечать.

Raymond Chen 04.04.2019 16:02

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

Nick Zuber 04.04.2019 16:03
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
1
2
815
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

В этом случае у вас есть один цикл i:=0..n и внутренний цикл j:=0..i-2. Это так?

Сложность внутреннего цикла будет O((n-1)/2), что является средним значением. Сложность внешнего for равна O(n).

Все, что вам нужно сделать, это умножить O((n)*(n/2)), то есть O(n²/2).

Если внутреннее значение для итераций отличается, его необходимо пересчитать.

Другие вопросы по теме