Может ли кто-нибудь предоставить базовый пример O-обозначения в Java? - PullRequest
Новая
       17

Может ли кто-нибудь предоставить базовый пример O-обозначения в Java?

1 голос
/ 06 января 2010

Я пытаюсь найти ограничения o нотаций, мне было интересно, был ли простой пример, демонстрирующий расширение для задачи, где версия 1 - это то же самое обозначение o, что и версия 2, но версия 2 работает более эффективно после улучшение

спасибо

Ответы [ 4 ]

6 голосов
/ 06 января 2010

В следующем коде добавление строки после // do something для выхода из внутреннего цикла оставляет более быструю функцию, но все же функцию O (n ^ 2). 

for (int i = 0; i < n; i++) {
   for (int j = 0; i < n; j++) {
        if (i == j) {
            // do something
        }
   }
}
3 голосов
/ 06 января 2010
Запись

O описывает ограничивающее поведение функции, наихудший случай для алгоритма. Обычно достаточно сравнить разные алгоритмы для одной и той же задачи, например, алгоритмы сортировки по этой функции.

Я бы сказал, что почти для всех алгоритмов (кроме алгоритмов O (1);)) всегда есть некоторые входные данные, которые заставляют алгоритм завершаться за меньшее время (или с меньшим потреблением памяти), чем обозначается описывающей нотацией O для этот алгоритм.

Предположим, у нас есть алгоритм подсчета, подобный этому: 

private int counter(int n) {
  int counter;
  for (int i = 0; i < 2; i++) {
    counter = 0;
    for (int i = 0; i < n; i++) {
      counter++;
    }
  }
  return counter;
}

Рост линейный, поэтому обозначение O для этого счетчика O (n) (я смотрю только на шаги, а не на память). Вы могли бы поспорить, что, эй, мы считаем дважды, и вместо этого напишите O (2n). Правда. Вы даже можете написать O (2n + c), чтобы указать, что нам нужны дополнительные шаги (время) для создания и инициализации локальной переменной.

Вот улучшенная реализация, которая все еще является линейной (O (n)), но завершается значительно быстрее: 

private int counter(int n) {
  int counter =0;
  for (int i = 0; i < n; i++) {
    counter++;
  }
  return counter;
}

Оба могут быть описаны как O (n) для обозначения линейного роста. Этого может быть достаточно, например, чтобы сравнить эти реализации с O (n ^ 2) или O (1) реализацией этого счетчика. Но чтобы сравнить «линейные» версии A и B, мы должны быть более точными и определить первую как O (2n), а вторую как O (n). Теперь сравнение значений нотации с O дает ожидаемый результат: реализация B «лучше».

0 голосов
/ 06 января 2010

Не может ли одна часть вопроса перевернуться? Так что если взять версию, которая работает без сбоев, сделайте ее более неэффективной, но таким образом, чтобы это не изменило исходный код. Например, добавление строки, чтобы программа спала в течение 10 секунд при выполнении некоторой работы, представляет собой постоянное изменение времени, которое, я думаю, будет удалено при вычислении big-O. В этом случае версия с дополнительным кодом будет версией 1, а другая - версией 2, которая более эффективна, но в несущественной форме.

Если кто-то хочет получить ответ в несколько более абстрактном смысле, поскольку big-O игнорирует члены более низкого порядка и постоянные множители, это может быть тем, где можно сделать что-то более эффективное без изменения общего big-O метода. Извините, у этого нет Java-кода, но этот ответ не зависит от языка.

0 голосов
/ 06 января 2010

Этот код сортировки слиянием работает в nLog (n): 

/**
 * Mergesort algorithm.
 * @param a an array of Comparable items.
 */
public static void mergeSort( Comparable [ ] a ) {
    Comparable [ ] tmpArray = new Comparable[ a.length ];
    mergeSort( a, tmpArray, 0, a.length - 1 );
}

/**
 * Internal method that makes recursive calls.
 * @param a an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param left the left-most index of the subarray.
 * @param right the right-most index of the subarray.
 */
private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,
        int left, int right ) {
    if( left < right ) {
        int center = ( left + right ) / 2;
        mergeSort( a, tmpArray, left, center );
        mergeSort( a, tmpArray, center + 1, right );
        merge( a, tmpArray, left, center + 1, right );
    }
}

/**
 * Internal method that merges two sorted halves of a subarray.
 * @param a an array of Comparable items.
 * @param tmpArray an array to place the merged result.
 * @param leftPos the left-most index of the subarray.
 * @param rightPos the index of the start of the second half.
 * @param rightEnd the right-most index of the subarray.
 */
private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
        int leftPos, int rightPos, int rightEnd ) {
    int leftEnd = rightPos - 1;
    int tmpPos = leftPos;
    int numElements = rightEnd - leftPos + 1;

    // Main loop
    while( leftPos <= leftEnd && rightPos <= rightEnd )
        if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];
        else
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];

    while( leftPos <= leftEnd )    // Copy rest of first half
        tmpArray[ tmpPos++ ] = a[ leftPos++ ];

    while( rightPos <= rightEnd )  // Copy rest of right half
        tmpArray[ tmpPos++ ] = a[ rightPos++ ];

    // Copy tmpArray back
    for( int i = 0; i < numElements; i++, rightEnd-- )
        a[ rightEnd ] = tmpArray[ rightEnd ];
}
...