У меня получилось 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];
}
}
Вы можете использовать короткую нотацию O для описания «строго нижних» отношений. Например, если у вас есть цикл, который всегда будет выполняться менее n раз, вы можете сказать, что его немного o(n)




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