Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Асимптотическая сложность алгоритмов
СообщениеДобавлено: 09 мар 2018, 16:19 
Не в сети
Начинающий
Зарегистрирован:
09 мар 2018, 15:20
Сообщений: 2
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Доброго времени суток!

Читаю книгу 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...

Буду весьма признателен за разъяснения.
Спасибо.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Асимптотическая сложность алгоритмов
СообщениеДобавлено: 09 мар 2018, 23:58 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
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)) шагов.
Не смотрел книгу, но это неудачный перевод. Он создает впечатление, что алгоритм вычисляет функцию f. (Когда я прочитал его в первый раз, я мысленно вставил слово "вычисления" после первого "для".) На самом деле 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 — размер задачи.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3D Homer "Спасибо" сказали:
Bush
 Заголовок сообщения: Re: Асимптотическая сложность алгоритмов
СообщениеДобавлено: 10 мар 2018, 08:28 
Не в сети
Начинающий
Зарегистрирован:
09 мар 2018, 15:20
Сообщений: 2
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Теперь понятно. Благодарю вас за ответ.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 3 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Асимптотическая устойчивость

в форуме Дифференциальные и Интегральные уравнения

Qller

6

310

21 май 2018, 14:13

Асимптотическая оценка по Де Брёйну

в форуме Ряды

UBIica_KoroLey_2004

5

221

02 мар 2020, 21:46

Асимптотическая нормальность оценки

в форуме Математическая статистика и Эконометрика

kstknlg

4

347

30 май 2020, 21:02

Асимптотическая эквивалентность интегралов

в форуме Интегральное исчисление

constantin01

0

193

21 июн 2019, 17:04

Задача на СМО (сложность)

в форуме Математическая статистика и Эконометрика

asya_X

0

226

05 июн 2017, 20:51

Сложность обратных задач в математике

в форуме Размышления по поводу и без

Hoper

7

495

21 дек 2018, 06:19

Сложность с внесением функции под знак дифференциала

в форуме Интегральное исчисление

OlNeva

0

206

04 дек 2018, 19:18

Сложность строения простых геометрических фигур

в форуме Геометрия

n1ko7

11

352

17 фев 2020, 20:07

Оценить сложность алгоритма. Очень помощь

в форуме Mathematica

Nattasha

0

499

26 мар 2017, 15:48

Решить задачу на схемную сложность булевой функции

в форуме Дискретная математика, Теория множеств и Логика

denisovviktor

4

244

29 май 2018, 13:38


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 7


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved