Java

Сложность алгоритмов. Теория алгоритмов. Программирование

Я вот недавно купил книгу про алгоритмы, книга называется "Алгоритмы. Теория и практическое применение". Написал эту книгу Род Стивенс. И там почти одной из первых тем была асимптотическая сложность алгоритма. Я первые дня не понимал о чем идет речь. Потом почитав отзывы понял что издательство Эксмо по кривожопски перевели её.И поэтому я в течении почти трех дней искал по поводу этого инфу в инете. Нашел книгу "Грокаем алгоритмы" и все вроде бы как прояснилось. Я еще чуть раньше до покупки книги про алгоритмы начал читать книгу по Java.И когда начал проходить оператор switch, то переписал код из неё и вроде как сам проанализировал его.
И вот я решил попробовать определить ту самую Асимптотическую сложность алгоритма. У меня получилось:
*Зная что у в case - блоках оператора switch стоят операторы break я выяснил, что сложность функции getDay и testDay будет константной, а большую часть компьютерных ресурсов "потребляют циклы". Поэтому я решил почти сразу перейти именно к циклу.
*Приняв факт, что асимптотическая сложность зависит в первую очередь от количества операций в программе, а соответственно и от объёма данных над которыми эти операции совершаются.
*В цикле for если присмотреться есть "диапазон "(хотя он явно не описан). И по моему мнению количество операций зависит от этого самого "диапазона"
*Так как цикл только один раз "перебирает значения этого "диапазона", то сложность алгоритма составляет O(N).
!Правильный ли у меня ход мыслей на этот счет???
!Правильно ли я определил асимптотическую сложность алгоритма???
Ринат Ахметов
Ринат Ахметов
113
а почему с таким вопросом именно в джаву, а не с/с++?
Ермек Каиржанов
Ермек Каиржанов
54 067
Лучший ответ
Ринат Ахметов Потому что Java из всех языков которые я начинал изучать, зашел мне больше всего.
Если я правильно понял из этого потока мыслей, что ты анализируешь сложность switch, то неправильно.
Ты делаешь предположение, что компилятор превращает switch в некий цикл, что является весьма волюнтаристским предположением. Почему бы компилятору, например, вместо этого не делать хеш-таблицу?
В общем, если ты САМ не крутишь какие-то циклы, то сложность СТАНДАРТНЫХ опраторов можно смело считать константой.
Максим Первеев
Максим Первеев
51 558
Ринат Ахметов Спасибо за ответ.
Тут дело в том, что в книге было написано - " команды выполняются не только в том case - блоке, где найдено совпадение значений, но и в следующих блоках. Чтобы выполнение команд прекратилось используют инструкцию break." Опираясь на это я провел анализ двух функций с оператором switch.
Ринат Ахметов В итоге я правильно определил сложность алгоритма?
Сложность - это зависимость времени выполнения алгоритма от размера входных данных. Если при увеличении количества входных данных в 5 раз программа будет выполняться примерно в 5 раз дольше - значит, это O(N), если в 25 раз дольше - то O(N^2). А если в любом случае будет примерно одинаково - то O(1). Но это не все, которые существуют, возможны практически любые комбинации математических операций и функций, например, O(N*log(N)), их расписывать не буду, думаю, и так понятно.
*$
*space* $$@$$
55 310
Ринат Ахметов Спасибо большое.
Во-первых, это теоретическая сложность, а не реальная. В теории сложности, если один алгоритм требует 1000n времени, а другой n времени, то у них одинаковая сложность - линейная зависимость от размера данных n. Таким образом, если ты обходишь данные циклом один раз, то это O(n), если там ещё вложенный цикл, то O(n^2). Проблемы возникают у алгоритмов, которым требуется экспоненциальное время O(2^n). Отсюда возникает класс проблем, именуемых нп-полными.
Александр Обрывин
Александр Обрывин
82 919

Похожие вопросы