Вопрос по количеству операций
Подскажите пожалуйста какую-нибудь литературу либо статью в инете.
Вот в задачнике по программированию в некоторых задачах стоит условие на количество операций (выполненных операторов присваивания). Допустим написано что число операций должно быть порядка 'n' либо порядка 'logN' либо пропорционально 'logN'. Еще не понятно допустим операции сложения вычитания умножения не учитываются при этом? Тоесть идет речь только о количестве операций присваивания?
Хотелось бы найти вот где почитать что-то, чтобы разобраться с этим вопросом в целом.
п.с. могу вставить условие задачи для примера.
Вот в задачнике по программированию в некоторых задачах стоит условие на количество операций (выполненных операторов присваивания). Допустим написано что число операций должно быть порядка 'n' либо порядка 'logN' либо пропорционально 'logN'. Еще не понятно допустим операции сложения вычитания умножения не учитываются при этом? Тоесть идет речь только о количестве операций присваивания?
Хотелось бы найти вот где почитать что-то, чтобы разобраться с этим вопросом в целом.
п.с. могу вставить условие задачи для примера.
Ну если написано
количество операций (выполненных операторов присваивания)
Цитата:
количество операций (выполненных операторов присваивания)
то значит считать только операторы присваивания. и с = а + е есть одна операция
не совсем понятно по поводу порядка числа. Вот написано что число А будет порядка числа N если A=C*N для некоторой константы C. Тогда если взять константу С сколь угодно большую, как же будет А порядка N?
Дело в том что если мы пропорционально увеличим N (а вот оно то может быть сколь угодно большим в отличие от константы C) то C можно будет пренебречь. Главное тут что зависимость линейная остается.
Буду благодарен если кто посоветует книжку по теме оценки сложностей алгоритмов, так сказать для начинающих, без заумной математики. )
Ну оценка сложности алгоритмов это не подсчет присваиваний. Кроме Кнута в голову ничего не приходит, и он - не то что вам хочется. Может гугл поможет статьей? Главное чтобы ее толковый человек написал.
могу посоветовать мейер б. бодуэн к. методы программирования -- довольно старая книжка но там есть главка по сложности алгоритмов, написано просто и понятно (только не помню том 1 или 2), в нете имеется
P.S. книжка сама по себе довольно интересная хоть и старая, для тех кто только начинает изучать программирование -- то что надо (если не обращать внимания на описания Фортрана и др. языков ))). дстоинство по сравнению с кнутом -- малый объём так что можно быстро освоить многие концептуально важные вещи, ну а потом уж можно и к кнуту приступить
P.S. книжка сама по себе довольно интересная хоть и старая, для тех кто только начинает изучать программирование -- то что надо (если не обращать внимания на описания Фортрана и др. языков ))). дстоинство по сравнению с кнутом -- малый объём так что можно быстро освоить многие концептуально важные вещи, ну а потом уж можно и к кнуту приступить
без сложной математики - сложно посоветовать. программирование - это в первую очередь математика.
Полезная книжка Кормен, Лизерсон, (третьего автора не помню).. Алгоритмы: построение и анализ
Полезная книжка Кормен, Лизерсон, (третьего автора не помню).. Алгоритмы: построение и анализ
Спасибо большущее за рекомендации, будем посмотреть )