Qual é o Big O de T (n)?

Eu tenho uma lição de casa que eu deveria encontrar a fórmula e a ordem de $T(n)$ dado por

T (1) = 1 T (n) = \frac{T (n - 1)}{T (n - 1) + 1} .

$T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\,.$

Eu estabeleci que $T(n) = \frac{1}{n}$ mas agora estou um pouco confuso. É $T(n) \in O(\frac{1}{n})$ a resposta correta para a segunda parte?

Com base na definição de big-O, temos que

O (g (n)) = {f (n) ∣ \exists c, n_{0} > 0 s.t. 0 \leq f (n) \leq c g (n) for all n \geq n_{0}} .

$O(g(n)) = \{f(n) \mid \exists c, n_0>0\text{ s.t. } 0\leq f(n) \leq cg(n)\text{ for all } n\geq n_0\}\,.$

Isso vale para $f(n) = g(n) = \frac{1}{n}$ então, com base na definição, $O(\frac{1}{n})$ deve estar correto, mas, no mundo real, é impossível que o algoritmo seja mais rápido do que $O(1)$ .

algorithm-analysis asymptotics recurrence-relation Karo
fonte

Respostas:

Sim, todas as funções $f(n)$ satisfazer $f(n) \in O(f(n))$ . As definições são significativas mesmo que $f(n)$ não é o tempo de execução de nenhuma função. De fato, essa notação vem da teoria dos números, onde $f(n)$ geralmente é algum termo de erro. Mesmo na ciência da computação, às vezes grandes notações de O são usadas ao analisar algoritmos para algo que não seja um tempo de execução ou requisitos de espaço.

Yuval Filmus
fonte

Parece que a diferença é que

T (n)

$T(n)$ cresce com

\frac{1}{n}

$\frac{1}{n}$ Como

n

$n$ aumenta, mas o número de operações para calcular

T (n)

$T(n)$ é

O (1)

$O(1)$ se você simplificar

T (n)

$T(n)$ para

T (n) = \frac{1}{n}

$T(n) = \frac{1}{n}$ ou

O (n^{2})

$O(n^2)$ se você usar a definição fornecida no problema de lição de casa diretamente.

24414 Kevin

@ Kevin A pergunta não diz nada sobre o número de operações necessárias para calcular qualquer coisa: apenas pede a solução para uma relação de recorrência. As soluções para recorrências não precisam ter tempos de execução para algoritmos, assim como os números não precisam ter comprimentos ou pesos.

David Richerby