Big-Oh обозначение расчета постоянных шагов

Question

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

Моя программа выглядит так. Он «всегда» принимает «48-битное» случайное начальное число и производит вывод, и фактические перемещения, которые происходят в процессе создания выходного сигнала, варьируются в зависимости от самого начального значения, а не от размера, потому что он фиксирован. Я зациклил этот процесс n раз, чтобы получить n выходов.

Означает ли это, что для моей программы нотация Big O является O (n)? Или я что-то совершенно не понимаю?

Итак, количество циклов, которые я просто пишу в коде. Например, если я установлю его на 1000, он получит 1000 входных семян и даст 1000 выходных данных. Процесс внутри цикла, поэтому число циклов for или количество операторов if - else или switch внутри большего цикла фиксировано. Единственное, что изменяется внутри большего цикла, это какой оператор if выбрать в зависимости от значения начального числа.

Answer 1

Строго говоря, O (n) означает, что это n является параметром / вводом алгоритма некоторого вида или производным от него. Это может быть длина ввода или даже вывода, но это происходит из параметра алгоритма.

Итак, это O (n) имеет значение, когда мы говорим о вашей процедуре «зациклить этот процесс n раз», если вы автоматизировали эту процедуру с помощью некоторого сценария. Сам алгоритм все еще работает в O (1) раз. Если вы не автоматизируете процедуру, просто забудьте о Big O - ручное действие делает ее неактуальной.

Answer 2

Сложность всегда выражается относительно что-то .

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

Пожалуй, наиболее полезной в вашем случае является информация о том, какова сложность относительно входного значения . Если это константа, вы можете сказать, что ваша программа работает в постоянное время , потому что независимо от того, каким будет (действительный) пользовательский ввод, время, которое потребуется вашей программе для вывода, будет примерно равно то же самое.

Answer 3

int f(int[] a, int[] b, int c) {
    int n = a.length;
    int m = b.length;
    int y = 0;
    for (int i = 0; i < n; ++i) {
        y += a[i];
        for (int j = 0; j < m; ++j) {
            y -= b[j];
        }
    }
    for (int k = 0; k < c; ++k) {
        y += 13;
    }
    return y;
}

Таким образом, сложность составляет O(n.m)+O(c) подсчет шагов (цикл, рекурсивные вызовы).

    for (long k = seed; k > 1; k /= 2) {
        ...;
    }

даст O(²log seed), максимум 48.