Пример большого кода O-O (log (n))

Подобно нотации Big O "O (1)", можно описать следующий код:

O(1):

    for (int i = 0; i < 10; i++) {
        // do stuff 
        a[i] = INT;
    }

O(n):

    for (int i = 0; i < n; i++) {
        // do stuff 
        a[i] = INT;
    }

O(n^2):
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // do stuff
            a[i][j] = INT;
        }
    }
  • Какой код O (log (n)) описывает?

Другой вопрос:

  • Какие решения существуют для "проблем с большими выводами" (что делать, когда вы получаете много данных в качестве ввода)?

Ответы

Ответ 1

Классический пример:

while (x > 0) {  
   x /= 2;  
}

Это будет:

Iteration |   x
----------+-------
    0     |   x
    1     |  x/2
    2     |  x/4
   ...    |  ...
   ...    |  ...
    k     |  x/2^k

2 k = x → Применение журнала в обе стороны → k = log (x)

Ответ 2

Из определения log (n) (я имею в виду здесь log с базой 2, но база действительно не имеет значения), это количество раз, что вам нужно умножить 2 на себя, чтобы получить n. Таким образом, пример кода O (log (n)):

i = 1
while(i < n)
    i = i * 2
    // maybe doing addition O(1) code

В реальных примерах кода вы можете встретить O (log (n)) в бинарном поиске, сбалансированных двоичных деревьях поиска, много resursive algoritmhs, очереди приоритетов.

Ответ 3

Для O (logn), пожалуйста, посмотрите на любой код, который включает стратегию разделения и завоевания Пример: Сортировка слияния и быстрая сортировка (ожидаемое время работы - O (nlogn) в этих случаях)

Ответ 5

Простейший код с циклом for, который вы бы использовали для представления:

O (1):

function O_1(i) {
    // console.log(i);
    return 1
}

О (п):

function O_N(n) {
    count = 0;
    for (i = 0; i < n; i++) {
        // console.log(i);
        count++;
    }
    return count
}

O (N²):

function O_N2(n) {
    count = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            // console.log(i, j);
            count++;
        }
    }
    return count
}

O (log_2 (п)):

function O_LOG_2(n) {
    count = 0;
    for (var i = 1; i < n; i = i * 2) {

        count++;
    }
    return count
}

O (SQRT (п)):

function O_SQRT(n) {
    count = 0;
    for (var i = 1; i * i < n; i++) {
        // console.log(i);
        count++;
    }
    return count
}

enter image description here

Ответ 6

Возможно, стоит подчеркнуть, что описанные ниже алгоритмы сложности являются подмножествами более сложных. Другими словами,

for (int i = 0; i < 10; i++) {
    // do stuff 
    a[i] = INT;
}

находится в O (1), но также и в O (n), O (n²), и, если вы хотите быть умным, O (log (n)). Почему? Поскольку все алгоритмы постоянного времени ограничены некоторыми линейными, квадратичными и т.д. Функциями.

Какие решения существуют для "проблем с большими O" (что делать, когда вы получаете много данных в качестве ввода)?

Этот вопрос не имеет для меня большого смысла. "Множество данных" довольно произвольно. Тем не менее, имейте в виду, что Big O не является единственной мерой сложности времени; помимо измерения наихудшей временной сложности, мы также можем рассмотреть случай наилучшего случая и средний, хотя это может быть немного сложнее рассчитать.

Ответ 7

В случае двоичного поиска вы пытаетесь найти максимальное количество итераций и, следовательно, максимальное количество раз, когда пространство поиска можно разделить пополам. Это достигается путем деления размера поискового пространства на n на 2 раза, пока вы не достигнете 1.

Пусть дается количество раз, когда вам нужно разделить n на 2 на метку x. Поскольку деление на 2, x раз эквивалентно делению на 2 ^ x, вам придется решить для этого уравнения:

n/2 ^ x = 1, которая становится n = 2 ^ x,

Итак, используя логарифм, x = log (n), поэтому BIG - O двоичного поиска O (log (n))

Повторить: x - это количество раз, когда вы можете разделить пространство размером n в два раза, прежде чем сузить его до размера 1.

http://www.quora.com/How-would-you-explain-O-log-n-in-algorithms-to-1st-year-undergrad-student