0
Как рассчитывается средняя сложность алгоритма? Хуже, очевидно, лучше, но как рассчитывается среднее значение?Как вычисляется средняя сложность
A
ответ
2
Средняя сложность работы (время, пространство и т. Д.) Определяется путем учета всех возможных входов заданного размера и определения асимптотической оценки среднего значения соответствующей меры на всех этих входах.
Например, средняя сложность «количества сравнений» для сортировки будет найдена, учитывая все N! перестановки ввода размера N и оценки оценок по среднему числу сравнений, выполняемых на всех этих входах.
I.e. это сумма чисел сравнений для всех возможных N! входы, разделенные N!
Поскольку средняя производительность на всех возможных входах равна ожидаемому значению одного и того же показателя производительности, средняя производительность также называется ожидаемой производительностью.
0
Quicksort представляет интересный нетривиальный пример расчета средней продолжительности выполнения. Как вы можете видеть, математика может стать довольно сложной, и, к сожалению, я не думаю, что существует общее уравнение для вычисления средней производительности.
2
рассчитать сложность для всех возможных входных и принимаемых и взвешенных сумм на основе их вероятностей. Это также называется ожидаемой runtine (аналогично ожиданию вероятностей).
ET(I) = P(X=I1)*T(I1) + P(X=I2)*T(I2) + P(X=I3)*T(I3).......
Смежные вопросы
- 1. Как вычисляется сложность следующего алгоритма?
- 2. Средняя сложность времени
- 3. Средняя сложность алгоритма
- 4. Средняя Cyclomatic Сложность нескольких файлов
- 5. Какова средняя временная сложность Bogosort?
- 6. худшая и средняя сложность алгоритма?
- 7. Амортизированная и средняя сложность выполнения
- 8. Средняя сложность случая - расчет линейного алгоритма
- 9. Какова средняя временная сложность для быстрой сортировки?
- 10. Средняя сложность времени нахождения элементов top-k
- 11. Сложность в случаях отличная, средняя и плохая
- 12. Средняя средняя
- 13. Средняя сложность кода для функции поиска в хэш-таблице
- 14. Mean расчет худший случай, лучший случай и средняя сложность случая
- 15. Средняя средняя размер сетки
- 16. Какова средняя временная сложность использования Set/TreeSet в java?
- 17. Как вычисляется использование ЦП?
- 18. Как вычисляется Linux MemFree
- 19. Как вычисляется факториал?
- 20. Как вычисляется Heading
- 21. JWT - как подпись вычисляется
- 22. Как вычисляется этот размер?
- 23. Knockout.js вычисляется
- 24. Почему unordered_multimap :: equal_range Средняя константа?
- 25. JS Как суммировать/Средняя?
- 26. Средняя и средняя фильтрация изображений в Java
- 27. Рекомендация системы - средняя средняя точность метрической оптимизации
- 28. Средняя средняя попарная корреляция в Python
- 29. Средняя средняя разница между sql и excel?
- 30. Netty TooLongFrameException: как вычисляется длина?
здесь ответ, в котором я вычислил ожидаемый runtine: - http://stackoverflow.com/questions/21719141/algorithm-analysis-expected-running-time-of-recursive-function-based-on- a-rng/21728256 # 21728256, используя ожидания –
Смутно связанная, ожидаемая глубина дерева, выбранного случайным образом из набора всех деревьев с N узлами, отличается от ожидаемой глубины дерева, сгенерированного добавлением узлов в случайные места. Подобные концепции делают расчет алгоритмических «средних» и «ожиданий» очень сложными, если вы не поняли, что вы измеряете. –