Big O обозначение предварительно обработанной статической структуры данных - PullRequest
Новая
       62

Big O обозначение предварительно обработанной статической структуры данных

0 голосов
/ 14 октября 2018

Насколько я понимаю, O (n) будет расти линейно по отношению к размеру входного набора данных.

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

Если я определю n как вход, массив ключей. 

def (arrOfKeys): 
    for key in arrOfKeys: # O(n) Iterating through the input.
        preprocessedList = getPreprocessedListDifferentForEachKey(key) # O(1) this list could have any number of elements.
        for anotherPreprocessedList in preprocessedList: # * <- O(n) or O(1)?
            for element in anotherPreprocessedList: # * <- O(n) or O(1)?
                ...
  • Я не уверен, что это O (1), потому что он предварительно обработан или O (n)так как размер списка зависит от того, что является входным параметром?

В конечном итоге это будет O (n ^ 3) в худшем случае, или можно утверждать, что O (n)?

1 Ответ

0 голосов
/ 15 октября 2018

Зависит от того, что если preprocessedList (и его подмассив) всегда будет иметь постоянную длину, ваши 2 внутренних цикла будут иметь временную сложность O (1).Однако если они зависят от входного аргумента arrOfKeys, каждый из них будет иметь значение O (n) и, следовательно, O (n) * O (n) = O (n ^ 2).

В сочетании с первымзатем вы умножаете его на его временную сложность, которая равна O (n).

Так что, если внутренние циклы - это каждый из O (n), это будет всего O (n ^ 3)

Если длина preprocessedList является переменной, но не зависит от длины arrOfKeys, вы можете определить ее как m и сказать, что она имеет временную сложность O (m).Затем вы можете сказать, что временная сложность равна O (n * m ^ 2).

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

...