Измерение сложности в алгоритмах с использованием автоматически инициализированных массивов

Question

Когда дело доходит до оценки временной сложности алгоритма, который использует массив, который должен быть инициализирован, обычно он выражается как O(k). Где k - размер массива.
Например, счетная сортировка имеет временную сложность O(n + k).

Но что происходит, когда массив автоматически инициализируется, как в Java или PHP. Было бы справедливо сказать, что счетная сортировка (или любой другой алгоритм, которому требуется инициализированный массив) в Java (или PHP ...) имеет временную сложность O(n)?

Answer 1

Вы говорите об этом http://en.wikipedia.org/wiki/Counting_sort, который имеет временную сложность O (n + k)?

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

Сложность времени все еще O(n + k)

Однако в реальной машине инициализация можетгораздо эффективнее, чем приращения, поэтому n и k напрямую не сопоставимы.Шаблон для инициализации подобен последовательному и очень эффективному (n).Например, если счет имеет тип int, ЦП может использовать long или 128-битные регистры для выполнения инициализации.

Схема доступа для подсчета, вероятно, будет относительно случайной и для большихзначения k могут быть намного медленнее.(до 10 раз медленнее)

Answer 2

Автоматическая инициализация не бесплатна , вы все равно должны это учитывать, так что она все равно O (n + k).

Answer 3

на самом деле это будет O(n+k)

таким образом, если n имеет более высокий порядок, чем k (много дубликатов при сортировке по счетам), то его можно отбросить за время, что делает его O(n)