Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 3 ] |
|
Автор | Сообщение | ||
---|---|---|---|
Bush |
|
||
Читаю книгу Rod Stephens "Essential Algorithms" (правда в русском переводе). В указанном англоязычном варианте у меня возникло некоторое непонимание на стр. 18, а в русском - на 30-й: Цитата: There are five basic rules for calculating an algorithm's Big O notation: 1. If an algorithm performs a certain sequence of steps f(N) times for a mathematical function f, it takes O(f(N)) steps. ... В русском варианте книги это выглядит так: Цитата: Существует пять основных правил для расчёта асимптотической сложности алгоритма. 1. Если для математической функции f алгоритму необходимо выполнить определёные действия f(N) раз, то для этого ему понадобится сделать O(f(N)) шагов. ... Красным цветом я выделил то, что вызывает у меня трудности в понимании... Мне были бы понятны фразы N раз и N шагов, в которых под N подразумевались бы какие-то целые числа. Но подсвеченные мною фразы сбивают меня с толку, т.к. под ними я понимаю вызов функции f с параметром N, а поскольку функции бывают разные, то в одном случае она может просто возвращать свой аргумент в качестве значения, т.е. N = f(N), а в другом - возвращать параметр в квадрате: N[math]^{2}[/math] = f(N). Т.е. я хочу сказать, что результат вызова f(N) сильно зависит от конкретной реализации функции f и результаты вызовов f(5), f(6), f(7) и т.д. могут изменяться совсем не линейно. Мне был бы предельно понятен такой вариант: Цитата: 1. If an algorithm performs a certain sequence of steps N times for a mathematical function f, it takes O(N) steps. Или на русском: Цитата: Если для математической функции f алгоритму необходимо выполнить определёные действия N раз, то для этого ему понадобится сделать O(N) шагов. Является ли такое, выполненное мною упрощение корректным? Если нет, то прошу пояснить почему. Не в последнюю очередь меня смущает и то, что на той же странице, чуть ниже, автор приводит пример для этого правила и резюмирует его такой фразой: Цитата: This algorithm examines each of the N items in the array once, so it has O(N) performance. Т.е. по сути, он написал именно тот упрощённый вариант, о котором я спрашиваю и который мне был бы понятным... Тогда я не понимаю причины того, почему изначально определение давалось в виде вызовов функции f... Буду весьма признателен за разъяснения. Спасибо. |
|||
Вернуться к началу | |||
3D Homer |
|
|
Bush писал(а): Цитата: 1. If an algorithm performs a certain sequence of steps f(N) times for a mathematical function f, it takes O(f(N)) steps. В русском варианте книги это выглядит так: Цитата: 1. Если для математической функции f алгоритму необходимо выполнить определёные действия f(N) раз, то для этого ему понадобится сделать O(f(N)) шагов. Представьте, что у вас есть процедура из 10 строк, которая вызывается для каждого элемента массива. Если каждый элемент рассматривается один раз, а всего их N, то количество исполненных строк в простейшем случае будет 10N. Но в более общем случае выполняются не все строки: например, там может быть условный оператор, и для разных элементов массива выполняются разные ветви этого оператора. Поэтому точное число строк будет [math]\le 10N[/math]. Но что если вместо строк C мы будем рассматривать инструкции ассемблера, и каждая строка C переводится в [math]\le 20[/math] инструкций? Тогда количество инструкций ассемблера будет [math]\le 20\cdot10N[/math]. Проще сказать, что число строк, инструкций и т.п. будет [math]O(N)[/math]: определение O большого и придумано для таких ситуаций. Теперь пусть алгоритм каждый элемент массива сравнивает с каждым другим элементом. Тогда каждый из N элементов рассматривается N раз, поэтому процедура из 10 строк вызывается [math]N^2[/math] раз. В данном случае книга говорит, что [math]f(N)=N^2[/math]. Опять в простейшем случае количество исполненных строк есть [math]10N^2[/math], но в более общем случае [math]O(N^2)[/math]. Есть еще более затратные алгоритмы, где какой-то кусок кода может вызываться [math]2^N[/math] или [math]N![/math] раз. В этом случае можно сказать, что сложность, в чем бы она не мерилась — в количестве строк на C, в инструкциях ассемблера, в миллисекундах и т.п. — есть, соответственно, [math]O(2^N)[/math] или [math]O(N!)[/math], где N — размер задачи. |
||
Вернуться к началу | ||
За это сообщение пользователю 3D Homer "Спасибо" сказали: Bush |
||
Bush |
|
||
Теперь понятно. Благодарю вас за ответ.
|
|||
Вернуться к началу | |||
[ Сообщений: 3 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Асимптотическая устойчивость | 6 |
310 |
21 май 2018, 14:13 |
|
Асимптотическая оценка по Де Брёйну
в форуме Ряды |
5 |
221 |
02 мар 2020, 21:46 |
|
Асимптотическая нормальность оценки | 4 |
347 |
30 май 2020, 21:02 |
|
Асимптотическая эквивалентность интегралов
в форуме Интегральное исчисление |
0 |
193 |
21 июн 2019, 17:04 |
|
Задача на СМО (сложность) | 0 |
226 |
05 июн 2017, 20:51 |
|
Сложность обратных задач в математике
в форуме Размышления по поводу и без |
7 |
495 |
21 дек 2018, 06:19 |
|
Сложность с внесением функции под знак дифференциала
в форуме Интегральное исчисление |
0 |
206 |
04 дек 2018, 19:18 |
|
Сложность строения простых геометрических фигур
в форуме Геометрия |
11 |
352 |
17 фев 2020, 20:07 |
|
Оценить сложность алгоритма. Очень помощь
в форуме Mathematica |
0 |
499 |
26 мар 2017, 15:48 |
|
Решить задачу на схемную сложность булевой функции | 4 |
244 |
29 май 2018, 13:38 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 7 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |