O que significa

15

O que significa logO(1)n ?

Estou ciente da notação big-O, mas essa notação não faz sentido para mim. Também não consigo encontrar nada sobre isso, porque não há como um mecanismo de pesquisa interpretar isso corretamente.

Para um pouco de contexto, a sentença em que a encontrei diz "[...] chamamos uma função [eficiente] se ela usa espaço O(logn) e, na maioria das vezes, logO(1)n por item".

Oebele
fonte
11
Concordo que não se deve escrever coisas assim, a menos que se tenha muita clareza sobre o que isso significa (e diga ao leitor o que é isso) e use as mesmas regras de maneira consistente.
Raphael
11
Sim, deve-se escrever como (log(n))O(1).
11
@RickyDemer Esse não é o ponto que Raphael está fazendo. significa exatamente ( log n ) b l a h . logblahn(logn)blah
David Richerby
4
@ Rafael Esta é a notação padrão em campo. Qualquer pessoa que conhece sabe o que isso significa.
Yuval Filmus 21/10
11
@YuvalFilmus Acho que a variedade de respostas discordantes é uma prova conclusiva de que sua alegação é falsa e que alguém deve realmente se abster de usar essa notação.
Raphael

Respostas:

16

Você precisa ignorar por um momento a forte sensação de que o " " está no lugar errado e continuar com a definição independentemente. f ( n ) = log O ( 1 ) n significa que existem constantes k e n 0 de tal modo que, para todos n n 0 , f ( n ) log k 1 n = log k n .Of(n)=logO(1)nkn0nn0f(n)logk1n=logkn

Observe que significa ( log n ) k . As funções do formato log O ( 1 ) n são freqüentemente chamadas de polilogarítmicas e você pode ouvir as pessoas dizerem " f é polylog  n ".logkn(logn)klogO(1)nfn

Você notará que é fácil provar que , já que 2 n k n para todos n 0 , onde k = 2 . Você pode estar se perguntando se 2 log n = log O ( 1 ) n . A resposta é sim, pois, para n grande o suficiente , log n 2 , então 2 log n log 2 n para tamanho grande o suficiente 2n=O(n)2nknn0k=22logn=logO(1)nnlogn22lognlog2n .n

Em uma nota relacionada, você frequentemente verá polinômios escritos como : mesma idéia.nO(1)

David Richerby
fonte
Isso não é suportado pela convenção comum de espaço reservado.
Raphael
Retiro meu comentário: você escreve em todos os lugares importantes, o que é suficiente.
Raphael
@Raphael OK. Eu ainda não tinha tido tempo de checá-lo, mas minha sensação era de que você poderia encomendar quantificadores de maneira diferente da minha. Na verdade, não tenho certeza se estamos definindo a mesma classe de funções.
David Richerby
Eu acho que você está definindo meu (2), e Tom define . cR>0{logcn}
Raphael
9

Este é um abuso de notação que pode ser entendido pela convenção de espaço reservado geralmente aceita : sempre que você encontrar um termo Landau , substitua-o (em sua mente ou no papel) por uma função arbitrária g O ( f ) .O(f)gO(f)

Então, se você encontrar

f(n)=logO(1)n

você deve ler

para alguns g O ( 1 ) .f(n)=logg(n)ngO(1).(1)

Observe a diferença de dizer " ao poder de alguma constante": g = n 1 / n é uma possibilidade distinta.logg=n1/n

Aviso: o autor pode estar empregando ainda mais abuso de notação e deseja que você leia

para alguns g O ( 1 ) .f(n)O(logg(n)n)gO(1).(2)

Observe a diferença entre (1) e (2); embora funcione para definir o mesmo conjunto de funções com valor positivo aqui, isso nem sempre funciona. Não mova em expressões sem cuidado!O

Rafael
fonte
3
Eu acho que o que faz isso acontecer é que é monotônico e suficientemente subjetivo para cada n fixo . Monotonic torna a posição do O equivalente e fornece (2) ⇒ (1); seguir o caminho inverso requer que exista g, o que poderia falhar se f ( n ) estiver fora do intervalo da função. Se você quiser salientar que mover O é perigoso e não cobre funções "selvagens", tudo bem, mas neste caso específico, é aceitável o tipo de função que representa custos. xlogx(n)nOgf(n)O
Gilles 'SO- stop be evil'
@Gilles enfraqueci a declaração para um aviso geral.
Raphael
11
Esta resposta foi muito editada e agora estou confuso: você agora afirma que (1) e (2) são efetivamente os mesmos?
Oebele
@ Obele Até onde eu sei, eles não são em geral, mas aqui.
Raphael
Mas, algo como não corresponde (1), mas faz jogo certo (2)? ou estou apenas sendo bobo agora? 3log2n
Oebele
6

Isso significa que a função cresce no máximo como à potência de alguma constante, ou seja, log 2 ( n ) ou log 5 ( n ) ou log 99999 ( n ) ...loglog2(n)log5(n)log99999(n)

Tom van der Zanden
fonte
Isso pode ser usado quando o crescimento da função é conhecido por estar limitado por alguma potência constante do , mas a constante específica é desconhecida ou deixada não especificada. log
precisa
Isso não é suportado pela convenção comum de espaço reservado.
Raphael
2

"At most logO(1)n" means that there is a constant c such that what is being measured is O(logcn).

In a more general context, f(n)logO(1)n is equivalent to the statement that there exists (possibly negative) constants a and b such that f(n)O(logan) and f(n)Ω(logbn).

It is easy to overlook the Ω(logbn) lower bound. In a setting where that would matter (which would be very uncommon if you're exclusively interested in studying asymptotic growth), you shouldn't have complete confidence that the author actually meant the lower bound, and would have to rely on the context to make sure.


The literal meaning of the notation logO(1)n is doing arithmetic on the family of functions, resulting in the family of all functions logg(n)n, where g(n)O(1). This works in pretty much the same as how multiplying O(g(n)) by h(n) results in O(g(n)h(n)), except that you get a result that isn't expressed so simply.


Since the details of the lower bound are in probably unfamiliar territory, it's worth looking at some counterexamples. Recall that any g(n)O(1) is bounded in magnitude; that there is a constant c such that for all sufficiently large n, |g(n)|<c.

g(n)<cg(n)>c.

This means, contrary to more typical uses of big-oh notation, functions that decrease too rapidly can fail to be in logO(1)n; for example,

1n=log(logn)/(loglogn)nlogO(1)n
because
lognloglognO(1)
The exponent here grows in magnitude too rapidly to be bounded by O(1).

A counterexample of a somewhat different sort is that 1logO(1)n.


fonte
Can't I just take b=0 and make your claimed lower bound go away?
David Richerby
1
@DavidRicherby No, b=0 still says that f is bounded below. Hurkyl: why isn't f(n)=1/n in logO(1)n?
Gilles 'SO- stop being evil'
@Gilles: More content added!
@Gilles OK, sure, it's bounded below by 1. Which is no bound at all for "most" applications of Landau notation in CS.
David Richerby
1) Your "move around O" rule does not always work, and I don't think "at most" usually has that meaning; it's just redundant. 2) Never does O imply a lower bound. That's when you use Θ. 3) If and how negative functions are dealt with by a given definition of O (even without abuse of notation) is not universally clear. Most definitions (in analysis of algorithms) exclude them. You seem to assume a definition that bounds the absolute value, which is fine.
Raphael