Необычные временные и пространственные сложности
Рассмотрим список A, состоящий из натуральных чисел. Есть ли следующий алгоритм
for i in range(sum(A)-min(A)):
print 'Hello world!'
иметь O(sum(A)-min(A)) сложность времени? Таблица общих временных сложностей ничего не говорит о таких функциях, как sum(), min() or max(),
И может ли сложность пространства следующего алгоритма быть выражена O(sum(A)-min(A)):
output = [True for i in range(sum(A)-min(A))]
2 ответа
В информатике временная сложность алгоритма количественно определяет количество времени, затрачиваемое алгоритмом на выполнение, как функцию длины строки, представляющей входные данные.
Строго говоря, наша функция временной сложности должна быть T(N), где N - длина ввода. Но иногда нелегко работать с простым размером ввода. Мы можем определить некоторые другие параметры, которые измеряют размер входных данных (например, в задачах с графами, которые мы часто используем |V| а также |E|).
В вашей ситуации ввод - это последовательность положительных целых чисел. Давайте определим новые параметры: n - количество целых чисел, и b - максимальное количество битов, которые могут представлять любое число на входе. N = O(n*b), Сложнее выразить сложность этого кода в (n, b) термины.
sum(A) = O(n * 2^b)
min(A) = O(2^b)
sum(A) - min(A) = O(n * 2^b)
reading input is O(n*b)
T(n, b) = O(n * 2^b)
Если вы хотите интерпретировать b как константа
T(n) = O(n)
Мы можем пойти дальше и определить maxn - максимальное число на входе. maxn = O(2^b),
sum(A) = O(n * maxn)
min(A) = O(maxn)
sum(A) - min(A) = O(n * maxn)
reading input is O(n * log(maxn))
T(n, maxn) = O(n * maxn)
Это более естественно, но не забывайте, что maxn является показателем действительной длины ввода числа.
Функции сложности имеют вид f (N), где N - размер задачи. Предложенные вами функции сложности не имеют такой формы и, следовательно, являются неверными.