Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 22.08.2007, 23:50
yamaxim

 
Сообщений: n/a

Как понимать O(N)
Объясните, пожалуйста, на пальцах - что такое O(N) (всмысле, конкретно что оно обозначает), как считается, и как проверяется. Если мне надо написать алгоритм со скоростью O(N) - что это значит и в какую сторону надо думать, чтобы так получилось. Заранее спасибо
  #2  
Старый 23.08.2007, 01:19
Аватар для Mystic
Новичок

Отправить личное сообщение для Mystic Посмотреть профиль Найти все сообщения от Mystic
 
Регистрация: 31.01.2007
Адрес: Москва, Зеленоград
Сообщений: 14

O(N) - оценка сложности алгоритма, т.е. твой алогоритм сложности порядка N (время выполнения зависит от N - количества чего-нибудь, например, элементов в массиве при поиске). Обычно это алгоритмы, состоящие из одного цикла, в котором просматриваются все элементы (можно и несколько циклов подряд, но не вложенных, тогда O(k*N) = O(N), где k - количество циклов).
ЗЫ: ответил примерно, без точных определений и, возможно, где-то неточно.
  #3  
Старый 23.08.2007, 13:12
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Вот ещё почитай http://algolist.ru/misc/o_n.php
  #4  
Старый 23.08.2007, 16:50
гость

 
Сообщений: n/a

Время работы алгоритма O(N) грубо говоря значит что его время работы (=число выполняемых элементарных операций в выбранной тобой модели вычислений, такой как RAM-машина) пропорционально размеру входа, т.е. не превышает c*N, для какой то константы c, при стремлении N к бесконечности.
  #5  
Старый 18.09.2007, 16:38
Новичок

Отправить личное сообщение для Даниил Алиевский Посмотреть профиль Найти все сообщения от Даниил Алиевский
 
Регистрация: 18.09.2007
Сообщений: 6

Запись y=O(x), где y - какая-либо функция x (например, время работы алгоритма, обрабатывающего x каких-то сущностей) означает буквально следующее: существует такая положительная константа c, что для всех x, бОльших некоторого достаточно большого значения x0, мы получим y<=cx. Обратите внимание на "достаточно большое значение" и на "константу c". Если сии значения велики, то для небольшого x может оказаться разумным предпочесть другой алгоритм, например, с временем O(N^2).

Еще один тонкий момент, о котором часто забывают: при оценке скорости алгоритма, обрабатывающего числа, разрядность числа обычно считается не влияющей на величину N. Поэтому, скажем, получается, что массив N 32-разрядных чисел можно отсортировать поразрядной сортировкой за O(N) операций (константа c здесь порядка 32) , что формально лучше O(N log N) у быстрой сортировки. Если при этом забыть, что для любого мыслимого числового массива log N не может быть больше логарифма объема диска, и что сортировка K-битовых чисел при больших K (скажем, криптографических ключей) потребует NK операций.
  #6  
Старый 23.09.2007, 01:33
Новичок

Отправить личное сообщение для it4.kp Посмотреть профиль Найти все сообщения от it4.kp
 
Регистрация: 23.09.2006
Адрес: Архангельск
Сообщений: 22

Добавлю еще пару моментов:

1. Разрядность числа обычно опускается в тех случаях когда она не превосходит разрядности чисел с которыми процессор умеет работать. То есть считается, то все базовые операции: +, -, *, / выполняются за O(1).

2. Часто сталкиваюсь с тем, как один говорит, например, этот алгоритм имеет сложность O(N^2), а другой ему отвечает, мол ты не прав, т.к. его сложность O(N). Так вот это не верно. Потому что если алгоритм имеет сложность O(N) то можно говорить, что он имеет сложность O(N^k) где k >= 1. То есть O() дает оценку сверху.
  #7  
Старый 06.01.2011, 02:19
гость12

 
Сообщений: n/a

народ во меня учител спросил мнения о O(n)-O(n)=0
я вроди как чаиник и толком не понил чо он имел виду...
помогите
  #8  
Старый 06.01.2011, 11:26
гocть

 
Сообщений: n/a

Сообщение от гость12 Посмотреть сообщение
O(n)-O(n)=0
неправда
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра