O que significa "O(1) o tempo de acesso" significa?
https://stackoverflow.com/questions/697918
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu já vi esse termo "O(1) o tempo de acesso" significa "rapidamente" mas eu não entendo o que isso significa.O outro termo que eu vejo com ele no mesmo contexto é "O(n) o tempo de acesso".Alguém por favor poderia explicar de uma forma simples o que esses termos significam?
Veja Também
Solução
Você vai querer ler em ordem de complexidade.
http://en.wikipedia.org/wiki/big_o_notation
Em suma, O (1) significa que leva um tempo constante, como 14 nanossegundos ou três minutos, independentemente da quantidade de dados no conjunto.
O (n) significa que leva uma quantidade de tempo linear com o tamanho do conjunto, portanto um conjunto duas vezes o tamanho levará o dobro do tempo. Você provavelmente não quer colocar um milhão de objetos em um deles.
Outras dicas
Em essência, Isso significa que leva a mesma quantidade de tempo para procurar um valor em sua coleção se você tem um pequeno número de itens em sua coleção, ou muito muito muito (dentro das limitações de hardware do seu computador)
O(n) significa que o tempo que leva para procurar um item é proporcional ao número de itens na coleção.
Exemplos típicos são estas matrizes, que podem ser acessados diretamente, independentemente de seu tamanho, e listas ligadas, que devem ser percorridas, desde o início, para aceder a um determinado item.
A operação geralmente discutido é inserir.Uma coleção pode ser O(1) para o acesso, mas O(n) para inserir.Na verdade uma matriz tem exatamente este comportamento, porque para inserir um item no meio, Você teria que mover cada item para a direita, copiando-o para o seguinte slot.
Cada resposta atualmente respondendo a esta pergunta diz que o O(1) significa tempo constante (o que quer que aconteça com a medição; pode ser tempo de execução, número de operações etc.). Isso não é preciso.
Dizer que o tempo de execução é O(1) significa que há uma constante c de modo que o tempo de execução seja limitado acima por c, independente da entrada. Por exemplo, retornando o primeiro elemento de uma matriz de n Inteiros é O(1):
int firstElement(int *a, int n) {
return a[0];
}
Mas esta função é O(1) também:
int identity(int i) {
if(i == 0) {
sleep(60 * 60 * 24 * 365);
}
return i;
}
O tempo de execução aqui é limitado acima em 1 ano, mas na maioria das vezes o tempo de execução é da ordem dos nanossegundos.
Dizer que o tempo de execução é O(n) significa que há uma constante c de modo que o tempo de execução seja limitado acima por c * n, Onde n mede o tamanho da entrada. Por exemplo, encontrar o número de ocorrências de um número inteiro particular em uma matriz não classificada de n números inteiros pelo algoritmo seguinte é O(n):
int count(int *a, int n, int item) {
int c = 0;
for(int i = 0; i < n; i++) {
if(a[i] == item) c++;
}
return c;
}
Isso ocorre porque precisamos iterar através da matriz inspecionando cada elemento um de cada vez.
O (1) significa que o tempo para acessar algo é independente do número de itens da coleção.
O (n) significaria que o tempo para acessar um item é proporcional ao número (n) dos itens da coleção.
O (1) não significa necessariamente "rapidamente". Isso significa que o tempo que leva é constante e não com base no tamanho da entrada para a função. Constante pode ser rápido ou lento. O (n) significa que o tempo que a função leva mudará em proporção direta ao tamanho da entrada da função, indicada por n. Novamente, pode ser rápido ou lento, mas ficará mais lento à medida que o tamanho de N aumenta.
É chamado de Grande notação o, e descreve o tempo de pesquisa de vários algoritmos.
O (1) significa que o pior tempo de execução é constante. Para a maioria das situações, significa que você não precisa procurar acitualmente para pesquisar a coleção, você encontra o que está procurando imediatamente.
"Big O notação" é uma maneira de expressar a velocidade dos algoritmos. n é a quantidade de dados com a qual o algoritmo está trabalhando. O(1) significa que, não importa quantos dados ele seja executado em tempo constante. O(n) significa que é proporcional à quantidade de dados.
O(1) Sempre execute ao mesmo tempo, independentemente do conjunto de dados n. Um exemplo de O (1) seria uma lista de Arrays acessando seu elemento com índice.
O(n) Também conhecido como ordem linear, o desempenho crescerá linearmente e em proporção direta ao tamanho dos dados de entrada. Um exemplo de O (n) seria uma inserção e exclusão da Arraylist em posição aleatória. Como cada inserção/exclusão subsequente em posição aleatória fará com que os elementos na lista de Arraylist mudem para a esquerda à direita de sua matriz interna, a fim de manter sua estrutura linear, sem mencionar sobre a criação de uma nova matriz e a cópia de elementos do antigo Para a nova matriz, que leva o tempo de processamento caro, portanto, prejudica o desempenho.
Basicamente, o (1) significa que seu tempo de computação é constante, enquanto o (n) significa que depende linealmente No tamanho da entrada - ou seja, o loop através de uma matriz possui O (n) - apenas em loop -, porque depende do número de itens, enquanto calcula o máximo entre os números ordinários tem (1).
A Wikipedia também pode ajudar: http://en.wikipedia.org/wiki/computational_complexity_theory
A maneira mais fácil de diferenciar O (1) e O (n) está comparando a matriz e a lista.
Para a matriz, se você tiver o valor do índice certo, poderá acessar os dados instantaneamente. (Se você não conhece o índice e precisa percorrer a matriz, então não será mais o (1))
Para a lista, você sempre precisa percorrer, se conhece o índice ou não.
Isso significa que o tempo de acesso é constante. Esteja você acessando de 100 ou 100.000 registros, o tempo de recuperação será o mesmo.
Por outro lado, o tempo de acesso o (n) indicaria que o tempo de recuperação é diretamente proporcional ao número de registros que você está acessando.
Isso significa que o acesso leva tempo constante, o IE não depende do tamanho do conjunto de dados. O (n) significa que o acesso dependerá do tamanho do conjunto de dados linearmente.
O O também é conhecido como Big-O.
Introdução aos algoritmos: Segunda edição de Cormen, Leiserson, Rivest & Stein diz na página 44 que
Como qualquer constante é um polinômio de grau-0, podemos expressar qualquer função constante como teta (n^0) ou teta (1). Essa última notação é um abuso pequeno, no entanto, porque não está claro qual variável está tendendo ao infinito. Frequentemente, usaremos a notação teta (1) para significar uma função constante ou constante em relação a alguma variável. ... Denotamos por O (g (n)) ... o conjunto de funções f (n) de modo que existem constantes positivas C e N0 tal que 0 <= f (n) <= c*g (n) para todos n> = n0. ... Observe que f (n) = teta (g (n)) implica f (n) = o (g (n)), pois a notação teta é mais forte que a notação.
Se um algoritmo é executado em O (1) tempo, significa que assintoticamente não depende de nenhuma variável, o que significa que existe pelo menos uma constante positiva que, quando multiplicada por um, é maior que a complexidade assintótica (~ tempo de execução) da função para valores de n acima de uma certa quantidade. Tecnicamente, é o tempo O (n^0).
Aqui está uma analogia simples; Imagine que você está baixando filmes online, com O (1), se levar 5 minutos para baixar um filme, ainda levará o mesmo tempo para baixar 20 filmes. Portanto, não importa quantos filmes você está baixando, eles levarão o mesmo tempo (5 minutos), seja um ou 20 filmes. Um exemplo normal dessa analogia é quando você vai a uma biblioteca de filmes, seja você está fazendo um filme ou 5, basta escolhê -los de uma só vez. Portanto, gastando o mesmo tempo.
No entanto, com O (n), se levar 5 minutos para baixar um filme, levará cerca de 50 minutos para baixar 10 filmes. Portanto, o tempo não é constante ou de alguma forma é proporcional ao número de filmes que você está baixando.
O (1) significa acesso aleatório. Em qualquer memória de acesso aleatório, o tempo necessário para acessar qualquer elemento em qualquer local é o mesmo. Aqui, o tempo pode ser qualquer número inteiro, mas a única coisa a lembrar é o tempo necessário para recuperar o elemento em (n-1) th ou enésimo local será o mesmo (ou seja, constante).
Enquanto O (n) depende do tamanho de n.
De acordo com minha perspectiva,
O (1) significa tempo para executar uma operação ou instrução de cada vez é uma, na análise de complexidade do tempo do algoritmo para o melhor caso.
