Предсказание теоретической эффективности среднего порядка и порядка роста алгоритма с использованием суммирования
Мне нужно спрогнозировать среднюю эффективность случая алгоритма по отношению к размеру его входов, используя суммирование / сигма-нотацию, чтобы прийти к окончательному ответу. Многие ресурсы используют суммирование для прогнозирования наихудшего случая, и я не смог найти человека, объясняющего, как прогнозировать средний случай, поэтому пошаговые ответы приветствуются.
Алгоритм содержит вложенный цикл for с основной операцией внутри самого внутреннего цикла:
[код отредактирован]РЕДАКТИРОВАТЬ: Выполнение базовой операции всегда будет выполняться внутри второго цикла for, если введен второй цикл for, и он не имеет операторов break или return. ОДНАКО: конец первого цикла for имеет оператор return, который зависит от значения, полученного в базовой операции, поэтому содержимое массива влияет на общее количество выполнений базовой операции для каждого запуска алгоритма.
Массив, переданный алгоритму, имеет случайно сгенерированное содержимое
Я думаю, что прогнозируемая средняя эффективность случая равна (n ^ 2) / 2, что делает n ^ 2 порядка роста / большой тета n ^ 2, но я не знаю, как теоретически доказать это с помощью суммирования.
Ответы очень ценятся!
Решение
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)
Другие решения
Других решений пока нет …