Предсказание теоретической эффективности среднего порядка и порядка роста алгоритма с использованием суммирования

Question

Предсказание теоретической эффективности среднего порядка и порядка роста алгоритма с использованием суммирования

Мне нужно спрогнозировать среднюю эффективность случая алгоритма по отношению к размеру его входов, используя суммирование / сигма-нотацию, чтобы прийти к окончательному ответу. Многие ресурсы используют суммирование для прогнозирования наихудшего случая, и я не смог найти человека, объясняющего, как прогнозировать средний случай, поэтому пошаговые ответы приветствуются.

Алгоритм содержит вложенный цикл for с основной операцией внутри самого внутреннего цикла:

[код отредактирован]

РЕДАКТИРОВАТЬ: Выполнение базовой операции всегда будет выполняться внутри второго цикла for, если введен второй цикл for, и он не имеет операторов break или return. ОДНАКО: конец первого цикла for имеет оператор return, который зависит от значения, полученного в базовой операции, поэтому содержимое массива влияет на общее количество выполнений базовой операции для каждого запуска алгоритма.

Массив, переданный алгоритму, имеет случайно сгенерированное содержимое

Я думаю, что прогнозируемая средняя эффективность случая равна (n ^ 2) / 2, что делает n ^ 2 порядка роста / большой тета n ^ 2, но я не знаю, как теоретически доказать это с помощью суммирования.
Ответы очень ценятся!

4

algorithm big-theta c++complexity-theory

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

TL; DR: Ваша сложность кода в среднем случае Θ(n²) если сложность «основной операции» Θ(1) и это не имеет return, break или же goto операторы.

Объяснение: сложность среднего случая — это просто ожидание количества операций в вашем коде с учетом размера ввода.

Скажем T(A, n) количество операций, которые ваш код выполняет с данным массивом A размера n, Это легко увидеть

T(A, n) = 1  +                // int k = ceil(size/2.0);
n * 2 + 1 +               // for (int i = 0; i < size; i++){
n * (n * 2 + 1) +         // for(int j = 0; j < size; j++){
n * n * X +               // //Basic operation
1                         // return (some int);

куда X количество операций в вашей «основной операции». Как мы можем видеть, T(A, n) не зависит от фактического содержимого массива A, Таким образом, ожидаемое количество операций с учетом размера массива (который является просто средним арифметическим T(A, n) для всех возможных A для данного n) точно равен каждому из них:

T(n) = T(A, n) = 3 + n * 2 + n * n * (2 + X)

Если мы предположим, что X = Θ(1)это выражение Θ(n²),

Даже без этого предположения мы можем получить оценку: если X = Θ(f(n)), тогда ваша сложность кода T(n) = Θ(f(n)n²), Например, если X является Θ(log n), T(n) = Θ(n² log n)

1