-3

Как мне вычислить O(N) для произвольного алгоритма и чему равно основание logN?

задан 4 Сен 12:32

1

Вопрос поставлен нелепо. Что значит "вычислить O(N)"? Ведь под O(N) понимается функция, которая растёт не быстрее линейной. Обычно O-символику в таком контексте используют для оценки сложности алгоритма. Но если алгоритм произволен, то сложность может быть выше линейной. И что в таком случае понимать под таким вычислением?

Основание логарифма в таких случаях всегда считается равным 2, хотя это не принципиально.

(4 Сен 13:30) falcao

@falcao: У меня есть алгоритм, в частности алгоритм решения задачи о рюкзаке, мне нужно вычислить его временную сложность О.

(4 Сен 14:09) DarKProGameR

Нарисуйте табличку в которой первый столбец это N - 1,2,3 и т.д. Второй столбец это время выполнения.

(4 Сен 14:51) mihailm
1

@DarKProGameR: в этом случае сложность может иметь вид O(N^2), или O(N^3), или O(2^n), или какую-то ещё. То есть сложность может быть выше линейной. И буква O здесь обозначает вовсе не сложность, а нечто другое. Смысл записи O(N) в том, что оцениваемая величина (сложность) растёт не быстрее CN, где C -- константа.

Если есть конкретный алгоритм, то надо проследить, что он делает, и отсюда получить оценку. Скажем, если там есть цикл длиной N, и на каждом шаге число операций (или время) линейно, то получится оценка O(N^2). Обычно для любого конкретного алгоритма оценка ясна почти сразу.

(4 Сен 15:50) falcao

@falcao: для этого необходим общий вид алгоритма или можно вычислить и через частный случай? У меня есть общий алгоритм, просто я не знаю как его записать

(4 Сен 16:14) DarKProGameR

@DarKProGameR: любой алгоритм конкретен, так как его можно реализовать при помощи программы. При этом не обязательно писать программный код: достаточно дать понятное словесное описание. Если его нет, то пока что нет и самого алгоритма.

Непонятно, что имеется в виду под "общим видом алгоритма". Частным случаем может быть ситуация с конкретным набором данных, на котором алгоритм работает такое-то время. Но её рассмотрение совершенно ни о чём не говорит.

По поводу способов оценки сложности алгоритма см. монографию Дональда Кнута, где это всё продемонстрировано на массе конкретных примеров.

(4 Сен 19:52) falcao

Я успел пораскинуть мозгами пока ждал ответа, получилось вот как: в шаге у меня постоянное количество операций, то есть С, а шагов в пределах от 2N+(N/2) до N^2, где N^2 в худшем случае, но даже если там N^3, то алгоритм всё равно похоже получается полиномиальным.

(4 Сен 20:13) DarKProGameR

@DarKProGameR: именно так и оценивается сложность алгоритмов. То есть ничего "сверхъестественного" в этом нет. Другое дело, что рассматриваемый алгоритм должен правильно решать задачу на любом наборе данных, и основная сложность относится именно к этой части. Если алгоритм в самом деле работает полиномиальное время, то это обычно сразу видно даже при очень грубых оценках.

(4 Сен 21:09) falcao

@falcao: получается алгоритм полиномиален, остается доказать, что он работает при любых наборах данных. И с чего мне начать? И забыл спросить, включается ли во временную сложность алгоритма и сортировка необходимая для использования алгоритма?

(4 Сен 21:21) DarKProGameR

@DarKProGameR: Поскольку Вы представляете на суд общественности какой-то алгоритм, а я не имею о нём никакого представления, то вопрос "с чего начать?" звучит странно. Если он разработан, то надо его прежде всего в понятном виде изложить. Что касается сортировки, то она происходит за полиномиальное время, то есть её наличие принципиально никак не влияет на сложность.

(5 Сен 1:48) falcao
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,287
×1,194
×1,040
×295
×106

задан
4 Сен 12:32

показан
137 раз

обновлен
5 Сен 1:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru