Notação Theta em tempo constante. Por que usamos o 1?

Na notação assintótica, quando se afirma que, se o tamanho do problema é pequeno o suficiente (por exemplo, n<cpara algumas constantes c), a solução leva tempo constante e é escrita como Theta(1).
Por que escrevemos 1 dentro do Theta?
O que 1significa isso? Por que não Theta(c)?

Essas notações destinam-se a denotar o crescimento assintótico. As constantes não crescem e, portanto, é praticamente igual a constante que você escolhe. No entanto, existe uma convenção de que você escolhe 1 para indicar nenhum crescimento.

Suponho que isso se deva ao fato de que você deseja simplificar os termos matemáticos em questão. Quando você tem um fator constante, apenas divida por ele e tudo o que resta é 1. Isso facilita as comparações.

Exemplo:

O (34 * n ^ 2) = O (1 * n ^ 2) = O (n ^ 2)

e

O (2567,2343 * n ^ 2/5) = O (n ^ 2)

Entendeu o que eu quis dizer? Como esses termos matemáticos se tornam cada vez mais complicados, você não deseja ter constantes ruidosas quando não são relevantes para as informações em que está interessado. Por que devo escrever O (2342.4534675767) quando é mais fácil expressar com O (1), que comunica os fatos do caso sem ambiguidade.

Além disso, o artigo da Wikipedia sobre complexidade de tempo também implica que é uma convenção:

Diz-se que um algoritmo é tempo constante (também escrito como tempo O (1)) ...

Tudo isso é muito ondulado, mas há uma razão matemática para não usarmos Theta (c) e, em vez disso, usar Theta (1). Usarei a notação Big O para mostrar isso.

Tem a ver com uma propriedade da notação Big Theta (assim como Big O e Big Omega). Se você tem uma função com taxa de crescimento O(g(x))e outra com taxa de crescimento O(c * g(x))onde cé constante, diria que elas têm a mesma taxa de crescimento. Isso éO(c * g(x)) = O(g(x))

Podemos dizer isso porque a definição da notação Big O ( f(x) = O(g(x))) significa que temos uma função f(x)e uma função g(x)tais que, |f(x)| <= k * |g(x)|para alguns valores constantes ke grandes o suficiente de x. Ao multiplicar pela constante c, teríamos:

O(c * g(x)) => k * |c * g(x)| = k * |c| * |g(x)| <= k' * g(x) Onde k' = k * |c|

Observe que, |k' * g(x)| <= k'' g(x)para alguns valores constantes k''e grandes o suficiente de x, o que significa k' * g(x)cresce a uma taxa de O(g(x))e, portanto,O(c * g(x)) = O(g(x))

Quando g(x) = 1, temos O(1)crescimento, dizer O(c)crescimento por algum valor de cnão nos diz nada, porque a constante já está incluída na definição da notação Big O. SimplificadoO(c) = O(1)

Bem, é claro que você poderia escrever Theta (c) (ou O (c)), mas por que isso difere de Theta (n)? n é apenas uma variável que indica o tamanho da entrada. Você pode escrever "A função é Theta (c) onde c é uma constante". O adendo importante é ... onde c é uma constante . Você precisa declarar explicitamente que um identificador não é uma variável.

Considere a teoria dos grafos em que os limites de um algoritmo são freqüentemente descritos como uma função de | V | e | E |, ou a contagem de nós e arestas, respectivamente. Então, pode ser prudente afirmar "A função é Theta (| V | * | E | ^ 2)".

Teta (1) no entanto é sempre uma constante - assumindo práticas matemáticas normais.

A notação teta é sobre crescimento em função de alguma variável - normalmente n. Se fosse necessário esclarecer qual variável se destina, a maneira de escrevê-la seria Theta (n ^ 0). A partir daí, é um passo simples para aplicar a identidade n ^ 0 = 1 (para n! = 0).

O ( c ) significa especificamente que a classe de algoritmos associada cresce linearmente com c , onde c é o tamanho de uma entrada para o algoritmo ou um parâmetro para o algoritmo . Não é o mesmo c que é usado para explicar a notação O, porque esse c é relevante apenas para a explicação, não para o uso. O ( c ) contém um c diferente que deve vir do contexto de entrada do algoritmo.