Articles of algoritmo

Existe um algoritmo de ordenação inteira O (n)?

Na semana passada eu tropecei neste artigo onde os autores mencionam na segunda página: Observe que isso gera um tempo de execução linear para pesos de borda inteira. O mesmo na terceira página: Isso produz um tempo de execução linear para ponderações de arestas inteiras e O (m log n) para sorting baseada em comparação. […]

Por que a constante sempre é descartada da grande análise O?

Estou tentando entender um aspecto particular da análise Big O no contexto de execução de programas em um PC. Suponha que eu tenha um algoritmo que tenha um desempenho de O (n + 2). Aqui, se n ficar muito grande, o 2 se torna insignificante. Neste caso, é perfeitamente claro que o desempenho real é […]

Subconjunto de sum com um tamanho de subconjunto fixo

O problema do subconjunto da sum afirma: Dado um conjunto de inteiros, existe um subconjunto não vazio cuja sum é zero? Este problema é NP-completo em geral. Estou curioso para saber se a complexidade desta ligeira variante é conhecida: Dado um conjunto de inteiros, existe um subconjunto de tamanho k cuja sum é zero? Por […]

Contando os swaps adjacentes necessários para converter uma permutação em outra

Recebemos duas sequências de letras do alfabeto latino em letras minúsculas. Eles são do mesmo tamanho e têm a mesma quantidade de tipos de letras (o primeiro tem um número igual de t’s como o segundo e assim por diante). Somos obrigados a encontrar o número mínimo de swaps ( por “swap” queremos mudar a […]

encontrar todos os subconjuntos que summ um determinado valor

Dado um conjunto de números: {1, 3, 2, 5, 4, 9}, encontre o número de subconjuntos que summ um valor específico (digamos, 9 para este exemplo). Isso é semelhante ao problema da sum do subconjunto com a pequena diferença de que, em vez de verificar se o conjunto tem um subconjunto que sum 9, precisamos […]

recursion versus iteração

É correto dizer que em toda parte a recursion é usada um loop for poderia ser usado? E se a recursion é geralmente mais lenta, qual é a razão técnica para usá-la na iteração de loop? E se é sempre possível converter uma recursion em um loop for, existe uma maneira prática de fazer isso?

O que é uma boa function hash?

O que é uma boa function Hash? Eu vi um monte de funções hash e aplicativos em meus cursos de estruturas de dados na faculdade, mas eu principalmente tenho que é muito difícil fazer uma boa function de hash. Como regra geral para evitar colisões, meu professor disse que: function Hash(key) return key mod PrimeNumber […]

Encontrando duplicatas no tempo O (n) e no espaço O (1)

Entrada: Dado um array de n elementos que contém elementos de 0 a n-1, com qualquer um desses números aparecendo qualquer número de vezes. Objetivo: Encontrar esses números repetidos em O (n) e usar apenas o espaço de memory constante. Por exemplo, se n for 7 e array for {1, 2, 3, 1, 3, 0, […]

Milhões de pontos 3D: como encontrar os 10 deles mais próximos de um determinado ponto?

Um ponto em 3-d é definido por (x, y, z). Distância d entre quaisquer dois pontos (X, Y, Z) e (x, y, z) é d = Sqrt [(Xx) ^ 2 + (Yy) ^ 2 + (Zz) ^ 2]. Agora há um milhão de inputs em um arquivo, cada input é algum ponto no espaço, em […]

Largura Primeiro Vs Profundidade Primeiro

Quando atravessando uma tree / gráfico Qual é a diferença entre Largura Primeiro e Profundidade primeiro? Qualquer codificação ou exemplo de pseudocódigo seria ótimo.