:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Сортировка » FAQ » Вопрос 1
  Вопрос 1




====================================================================
> 1.  Ликбез для понимания важной информации: 
>    Что означает символ O(n) ? Оценки Omega() и Theta()
>    Почему _не пишется_ основание логарифма: O(logn) ?  
====================================================================

                  Оценки времени исполнения. Cимвол O().

         Для оценки производительности алгоритмов можно использовать
    разные подходы. Самый бесхитростный - просто запустить каждый
    алгоритм на нескольких задачах и сравнить время исполнения. Другой
    способ - оценить время исполнения через символ O(n) (читается так:
    о большое от n). n здесь - обычно количество обрабатываемых элементов
    данных (например, сортируемых чисел). 
         Также такую оценку называют 'асимптотикой', так как она обозначает
    асимптотическое поведение алгоритма ( n -> беск. )

         Когда используют обозначение O(), имеют в виду не точное время
    исполнения, а только его предел сверху, причем с точностью до
    постоянного множителя. Когда говорят, например, что алгоритму
    требуется время порядка O(n^2), имеют в виду, что время исполнения
    задачи растет не быстрее, чем квадрат количества элементов. Чтобы
    почувствовать, что это такое, посмотрите на таблицу, где приведены
    числа, иллюстрирующие скорость роста для нескольких разных функций.

          n        log n     n*log n             n^2

      1            0       0             1

      16           4       64            256

      256          8       2,048         65,536

      4,096        12      49,152        16,777,216

      65,536       16      1,048,565     4,294,967,296

      1,048,476    20      20,969,520    1,099,301,922,576

      16,775,616   24      402,614,784   281,421,292,179,456

         Если считать, что числа в таблице соответствуют микросекундам,
    то для задачи с 1048476 элементами алгоритму с временем работы
    O(log n) потребуется 20 микросекунд, а алгоритму с временем работы
    O(n^2) - более 12 дней.

>     Если оба алгоритма, например, O ( n*log n ), то это отнюдь
>    не значит, что они одинаково эффективны.

    Символ О не учитывает константу, то есть первый может быть, скажем
    в 1000 раз эффективнее. Это значит лишь то, что время (или требуемая 
    память или что-либо еще, что надо оценить) возрастает приблизительно 
    c такой же скоростью, как функция n*log n.

>    За функцию берется количество операций, возрастающее быстрее всего.

      То есть если в программе одна функция выполняется O(n) раз -
    например, умножение, а сложение - O(n^2) раз, то общая сложность -
    O(n^2), так как n^2 возрастает быстрее. 
      Практический смысл этого в нашем случае такой: при увеличении n 
    более быстрые ( в определенное, константное число раз ) сложения
    станут выполнятся настолько часто, что будут влиять на производительность
    много сильнее, нежели медленные, но редкие умножения. 

>    Основание логарифма не пишется.

    Причина этого весьма проста. Пусть у нас есть 
       O( log n ). Перейдем к основанию 3: log n = log n / log 2.
             2                                2       3       3       
        Hо 1/log 2, как и любую константу, асимптотика - символ O()
                3
    не учитывает. Таким образом, O(log n) = O(log n).
                                      2          3
    К любому основанию мы можем перейти аналогично, а, значит, и писать
    его не имеет смысла.

    В заключение, привожу формальную трактовку обозначения O(g(n)) для
   положительных функций f(n), g(n):
   
    Опp.1 O(g(n)) - множество функций f(n), для котоpых существуют
          положительные константы c, n0, такие что
               f(n) <= c*g(n) для всех n>=n0

    Опp.2 Запись f(n) = O(g(n)) означает, что f(n) - элемент множества
          O(g(n))
   
    Иногда символ O() используют в более широком смысле, подразумевая не
    только верхнюю, но и нижнюю оценку Theta(): существуют c1, c2, n0 > 0:
           0 <= c1*g(n) <= f(n) <= c2*g(n), n>=n0        
   
    Кроме символа O() используются также оценки

        Omega(g(n)) - нижняя оценка: множество f(n): существуют c, n0>0:
      c*g(n) <= f(n)
	  
        Theta(g(n)) - комбинация O() и Omega(): точная оценка асимптотики.
       Theta(g(n) - множество f(n): существуют c1, c2, n0>0: 
           0 <= c1*g(n) <= f(n) <= c2*g(n), n>=n0        
    
    Все описанные свойства оценки O() также верны для Omega() и Theta().

    Интуитивный смысл оценок:
     f = O(g) - f растет не быстрее g         }
     f = Omega(g) - f растет не медленнее g   } при n->00
     f = Theta(g) - f растет так же, как g    }