1 | |||||||||||
Как вычислять сложность алгоритма, или найти асимптотическую сложность любой программки?11.06.2017, 13:31. Показов 8777. Ответов 1
Метки нет (Все метки)
Например
Вычислить x^n по алгоритму быстрого возведения в степень Добавлено через 43 секунды
Из анализа данного алгоритма известно, что его асимптотическая сложность порядка O(log2n). Как найти данный логарифм. Есть ли простой способ, как например перевод чисел из одной системы в другую, запомнил и используешь? Добавлено через 1 минуту А если такая программулина, нужно разобраться в данном вопросе, или я не прав насче , нужно осмыслить тему асимптотическая сложность алгоритмов. Какая тут сложность?
0
|
11.06.2017, 13:31 | |
Ответы с готовыми решениями:
1
Определить тип сортировки и её асимптотическую сложность Найти сложность алгоритма Найти временную и емкостную сложность алгоритма Как расчитывать сложность алгоритма |
Модератор
9956 / 5313 / 3327
Регистрация: 17.08.2012
Сообщений: 16,219
|
|
13.06.2017, 16:55 | 2 |
HaydoSpeed, можете считать, что O(что-то там) - это количество итераций цикла, необходимое для окончания вычислений при наихудшем случае (максимальное количество итераций). При этом берите в расчёт только целевую часть алгоритма, а не программу в целом.
При быстром возведении в степень число n делится на два до тех пор, пока не станет равным 1. найдём количество итераций k, необходимых для этого. Каждую итерацию n делится на 2, при последней итерации n будет разделено на 2k, то есть: Находим это самое k, и дело в шляпе. Количество итераций - это и есть сложность алгоритма, то есть, можно записать, что сложность алгоритма быстрого возведения в степень есть O(log2n). Теперь оценим сложность алгоритма для второй программы. Не принимаем во внимание ввод-вывод и прочую подготовку данных. Целевым алгоритмом в данном случае можно считать сортировку выбором, то есть, строки 30 и 31. Очевидно, что количество итераций будет Можно, конечно, абсолютно точно записать, что сложность сортировки будет Однако, при асимптотическом анализе алгоритмов считается, что n → ∞, а постоянные множители не учитываются. Поэтому выбрасываем слагаемые при n и деление на 2. Окончательно, сложность алгоритма сортировки выбором будет O(n2). Ещё в Вашей второй программе можно принять для анализа алгоритм поиска элемента массива (строки 37 и 38). Очевидно, что в худшем случае будут просмотрены все n элементов, иными словами, сложность этого алгоритма O(n).
2
|
13.06.2017, 16:55 | |
13.06.2017, 16:55 | |
Помогаю со студенческими работами здесь
2
Как оценить сложность алгоритма? Как рассчитать сложность алгоритма? Как определить временную сложность алгоритма? Как узнать сложность алгоритма(ресурсы ,способы) сложность алгоритма Сложность Алгоритма Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |