É a complexidade temporal do algoritmo vazio O(0)?

É preciso o mesmo tempo para correr independentemente da entrada, portanto é O(1) por definição.

Várias respostas dizem que a complexidade é O(1) porque o tempo é uma constante e o tempo é limitado pelo produto de algum coeficiente e 1. Bem, é verdade que o tempo é uma constante e é limitado dessa forma, mas isso não significa que a melhor resposta é O(1).

Considere um algoritmo que funciona em tempo linear. É normalmente designado como O (n), Mas vamos fazer de advogado do diabo. O tempo é limitado pelo produto de algum coeficiente e n ^ 2. Se considerarmos O (n^2) para ser um conjunto, o conjunto de todos os algoritmos cuja complexidade é pequena o suficiente, então algoritmos lineares estão nesse conjunto. Mas isso não significa que a melhor resposta é O(n^2).

O algoritmo vazio está em o(n^2) e em O(n) e em O(1) e em o (0). Voto em O (0).

Eu tenho um argumento muito simples para o algoritmo vazio sendo O (0): para qualquer função f(x), f(x) está em O(f(x)). Simply let f (x)=0, and we have that 0(the runtime of the empty algorithm) is in O (0).

Em uma nota lateral, eu odeio quando as pessoas escrevem f(x) = O(g(x)), quando deve ser f(x) ∈ o(g (x)).

O Grande O é Notação assintótica. Para usar big O, você precisa de uma função - em outras palavras, a expressão deve ser parametrizada por n, mesmo que n não seja usado. Não faz sentido dizer que o número 5 é O(n), é a função constante f(n) = 5 que é O(n).

Então, para analisar a complexidade do Tempo em termos de Big O você precisa de uma função de n. o seu algoritmo sempre faz indiscutivelmente 0 passos, mas sem um parâmetro variável falar sobre comportamento assintótico não faz sentido. Suponha que seu algoritmo é parametrizado por N. só agora você pode usar Notação assintótica. Não faz sentido dizer que é O(n²), ou mesmo O (1), Se você não especificar o que é n(ou a variável escondida em O (1))!

Assim que se estabelece o número de passos, é uma questão da definição de big O: A função f(n) = 0 é O(0).

Uma vez que esta é uma questão de baixo nível depende do modelo de cálculo. Sob suposições "idealistas", é possível que você não faça qualquer. Mas em Python, você não pode dizer {[[0]}, mas apenas def f(x): pass. Se você assumir que toda a instrução, mesmo pass (NOP), leva tempo, então a complexidade é f(n) = c, para alguma constante c, e, a menos que c != 0 você só pode dizer que f é O(1), não O(0).

Vale a pena notar que o big O, por si só, não tem nada a ver com algoritmos. Por exemplo, você pode dizer sin x = x + O (x³) ao discutir a expansão do Taylor. Além disso, O(1) não significa constante, significa limitada por constante.

Todas as respostas até agora abordam a questão como se houvesse uma resposta certa e errada. A questão é uma questão de definição. Normalmente na teoria da complexidade o custo do tempo é um inteiro - - - embora isso também seja apenas uma definição. Você está livre para dizer que o algoritmo vazio que sai imediatamente leva 0 passos de tempo ou 1 passo de tempo. É uma pergunta abstrata porque a complexidade do tempo é uma definição abstrata. No mundo real, nem sequer tens passos temporais., você tem tempo físico contínuo; pode ser verdade que uma CPU tem ciclos de clock, mas um computador paralelo poderia facilmente ter Relógios assíncronos e, em qualquer caso, um ciclo de clock é extremamente pequeno. Dito isto, eu diria que é mais razoável dizer que a operação de parada leva um passo de tempo em vez de que leva 0 passos de tempo. Parece mais realista. Para muitas situações é indiscutivelmente muito conservador, porque a sobrecarga da inicialização é tipicamente muito maior do que executar uma operação aritmética ou lógica. Dar o algoritmo vazio 0 passos de tempo só seria razoável modelar, por exemplo, uma chamada de função que é deletada por um compilador otimizador que sabe que a função não fará nada.

Deve ser O(1). O coeficiente é sempre 1.

Considere:

Se algo cresce como 5n, você não diz O( 5n), você diz O(n) [em outras palavras, o(1n)]

Se algo crescer como o 7n ^ 2, Você não diz O(7n^2), você diz O (n^2) [em outras palavras, O (1n^2)]

Da mesma forma você deve dizer O(1), não o(alguma outra constante)

Não existe tal coisa como O(0). Mesmo uma máquina oracle ou um hypercomputador requerem o tempo para uma operação, isto é solve(the_goldbach_conjecture), ergo:

Todas as máquinas, teóricas ou reais, finitas ou infinitas produzem algoritmos com uma complexidade mínima de tempo de O(1).

Mas este código aqui é ... O(0):

// Hello world!

:)

, eu diria que é O(1) por definição, mas O(0) se você deseja obter técnicas sobre o assunto: desde que O(k₁g(n)) é equivalente a O(k₂g(n)) para quaisquer constantes k₁ e k₂, segue-se que S(1 * 1) é equivalente a O(0 * 1), e, portanto, S(0) é equivalente a O(1).

No entanto, o algoritmo vazio não é como, por exemplo, a função identidade, cuja definição é algo como "devolver a sua entrada". O algoritmo vazio é mais como um declaração vazia, ou o que quer que aconteça entre duas declarações. Sua definição é "não fazer absolutamente nada com sua entrada", presumivelmente sem mesmo a sobrecarga implícita de simplesmente ter entrada.

Consequentemente, a complexidade do algoritmo vazio é única na medida em que O(0) tem uma complexidade de zero vezes qualquer função que lhe agrade, ou simplesmente zero. Segue - se que, uma vez que todo o negócio é tão louco, e desde O(0) já não significa algo útil, e uma vez que é um pouco ridículo até mesmo discutir tais coisas, um razoável caso especial para O (0) é algo como isto:

A complexidade do algoritmo vazio é O (0) no tempo e espaço. Um algoritmo com complexidade de tempo O (0) é equivalente ao algoritmo vazio.

Pronto.

Dada a definição formal de Big O:

Seja f (x) e g(x) duas funções definidas sobre o conjunto de números reais. Depois, escrevemos:

f(x) = O(g(x)) à medida que x se aproxima do Infinito, Existe um M real e um x0 real de modo que:

|f(x)| <= M * |g(x)| for every x > x0

Na minha opinião, se substituirmos g (x) = 0 (a fim de termos um programa com complexidade O (0)), devemos ter:

|f(x)| <= 0, para cada x > x0 (a restrição da existência de um m real e x0 é praticamente levantada toma.

Que só pode ser verdadeiro quando f (x) = 0.

Então eu diria que não só o programa vazio é O(0), mas é o único para o qual isso se mantém. Intuitivamente, isso deveria ter sido verdade uma vez que O(1) abrange todos os algoritmos que requerem um número constante de passos, independentemente do tamanho de sua tarefa, incluindo 0. É essencialmente inútil falar sobre O (0); já está em O(1). Eu suspeito que é puramente por simplicidade de definição que nós usamos O(1), onde poderia muito bem ser Ou algo parecido.

0 = o(f) para toda a função f, Uma vez que 0

O (1) significa que a complexidade temporal do algoritmo é sempre constante.

Digamos que temos este algoritmo (Em C):

void doSomething(int[] n)
{
  int x = n[0]; // This line is accessing an array position, so it is time consuming.
  int y = n[1]; // Same here.
  return x + y;
}

Estou ignorando o fato de que o array pode ter menos de 2 posições, só para mantê-lo simples. Se contarmos as duas linhas mais caras, temos um tempo total de 2.

2 = o(1), Porque:

2 1

Se tivermos este código:

public void doNothing(){}

E contamo-lo como tendo 0 linhas expansivas, não há diferença em dizer que tem O (0) o(1), ou o(1000), porque para cada uma dessas funções, podemos provar o mesmo teorema.

Normalmente, se o algoritmo toma um número constante de passos para completar, dizemos que tem o(1) complexidade de tempo.

Eu acho que isto é apenas uma convenção, porque você poderia usar qualquer número constante para representar a função dentro do O().

Não. É o (C) por convenção sempre que você não tem dependência do tamanho da entrada, onde c é qualquer constante positiva(tipicamente 1 é usado - O(1) = o (12.37)).