Acesso mais rápido do que o navegador!
61 relações: Acoplamento (teoria dos grafos), Algoritmo, Algoritmo de aproximação, Algoritmo de busca de expressões Boyer-Moore, Algoritmo de Ukkonen, Algoritmo probabilístico, Análise amortizada, Aritmética de Presburger, Arranjo (computação), Avi Wigderson, BPP, Bubble sort, Busca por força bruta, Cadeia de caracteres, Christos Papadimitriou, Ciência da computação, Classe de complexidade, Coloração de grafos, Complexidade computacional, Complexidade de caso médio, Complexidade de pior caso, Computação paralela, Conjunto de instruções, Correlação parcial, DLOGTIME, Exptime, Fatoração de inteiros, Função de Ackermann, Função polinomial, Grande-O, Heapsort, Identidades logarítmicas, Insertion sort, Intro sort, László Babai, László Lovász, Limitantes superiores e inferiores, Logaritmo, Logaritmo iterado, Merge sort, Michael Sipser, Modelo de computação, Ordenação por comparação, Otimização, P (complexidade), Pesquisa binária, Problema de decisão, Problema de isomorfismo de grafos, Problema do caixeiro-viajante, Programação dinâmica, ..., Programação linear, Quicksort, Sistema de numeração binário, Smoothsort, Teorema da convolução, Teoria dos grafos, Tese de Cobham, Teste de primalidade AKS, Transformada rápida de Fourier, União-busca, 2-EXPTIME. Expandir índice (11 mais) »
Acoplamento (teoria dos grafos)
Na teoria dos grafos um acoplamento, emparelhamento ou conjunto de arestas independentes em um grafo G é um conjunto de '''arestas''' sem vértices em comum.
Novo!!: Complexidade temporal e Acoplamento (teoria dos grafos) · Veja mais »
Algoritmo
Uma animação do algoritmo de ordenação quicksort de uma matriz de valores ao acaso. As barras vermelhas marcam o elemento pivô. No início da animação, estando o elemento para o lado direito, é escolhido como o pivô Em matemática e ciência da computação, um algoritmo é uma sequência finita de ações executáveis que visam obter uma solução para um determinado tipo de problema.
Novo!!: Complexidade temporal e Algoritmo · Veja mais »
Algoritmo de aproximação
Em ciência da computação e pesquisa operacional (PO), algoritmos de aproximação são algoritmos usados para encontrar soluções aproximadas em problemas de otimização.
Novo!!: Complexidade temporal e Algoritmo de aproximação · Veja mais »
Algoritmo de busca de expressões Boyer-Moore
Em ciência da computação, o algoritmo de busca de expressões Boyer-Moore (Boyer-Moore string search algorithm) é um eficiente algoritmo de busca que é o padrão de qualidade para busca prática de expressões em literatura.
Novo!!: Complexidade temporal e Algoritmo de busca de expressões Boyer-Moore · Veja mais »
Algoritmo de Ukkonen
Em ciência da computação, o algoritmo de Ukkonen é um algoritmo online de tempo linear para construção de árvores de sufixos, proposto por Esko Ukkonen em 1995.
Novo!!: Complexidade temporal e Algoritmo de Ukkonen · Veja mais »
Algoritmo probabilístico
Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica.
Novo!!: Complexidade temporal e Algoritmo probabilístico · Veja mais »
Análise amortizada
Na ciência da computação, análise amortizada é um método para analisar a complexidade de tempo de um algoritmo ou quantos recursos computacionais, especialmente de tempo ou de memória no contexto de programas de computadores, ele leva para executar.
Novo!!: Complexidade temporal e Análise amortizada · Veja mais »
Aritmética de Presburger
A Aritmética de Presburger é uma teoria de primeira-ordem dos números naturais com soma.
Novo!!: Complexidade temporal e Aritmética de Presburger · Veja mais »
Arranjo (computação)
Em programação de computadores, um arranjo (em inglês array) é uma estrutura de dados que armazena uma coleção de elementos de tal forma que cada um dos elementos possa ser identificado por, pelo menos, um índice ou uma chave.
Novo!!: Complexidade temporal e Arranjo (computação) · Veja mais »
Avi Wigderson
Avi Wigderson (אבי ויגדרזון) é um matemático e informático israelense.
Novo!!: Complexidade temporal e Avi Wigderson · Veja mais »
BPP
Na teoria da complexidade computacional, BPP (inglês: Bounded-error Probabilistic Polinomial time, probabilístico de tempo polinomial comprometido à erros) é a classe de problemas de decisão solúveis por uma Máquina de Turing em tempo polinomial, com uma probabilidade de erro de no máximo 1/3 para todas as instâncias.
Novo!!: Complexidade temporal e BPP · Veja mais »
Bubble sort
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples.
Novo!!: Complexidade temporal e Bubble sort · Veja mais »
Busca por força bruta
Em ciência da computação, busca por força bruta ou busca exaustiva, também conhecido como gerar e testar, é uma técnica de solução de problemas trivial, porém muito geral que consiste em enumerar todos os possíveis candidatos da solução e checar cada candidato para saber se ele satisfaz o enunciado do problema.
Novo!!: Complexidade temporal e Busca por força bruta · Veja mais »
Cadeia de caracteres
Na programação de computadores, uma cadeia de caracteres ou string é uma sequência de caracteres, geralmente utilizada para representar palavras, frases ou textos de um programa.
Novo!!: Complexidade temporal e Cadeia de caracteres · Veja mais »
Christos Papadimitriou
Christos Harilaos Papadimitriou (em grego: Χρήστος ΧαριλάουΠαπαδημητρίου; Atenas) é um Cientista da Computação da divisão de Ciência da Computação da Universidade da Califórnia em Berkeley, Estados Unidos.
Novo!!: Complexidade temporal e Christos Papadimitriou · Veja mais »
Ciência da computação
A Ciência da Computação lida com fundamentos teóricos da informação, computação, e técnicas práticas para suas implementações e aplicações.
Novo!!: Complexidade temporal e Ciência da computação · Veja mais »
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: Complexidade temporal e Classe de complexidade · Veja mais »
Coloração de grafos
Em teoria dos grafos, coloração de grafos é um caso especial de rotulagem de grafos; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições.
Novo!!: Complexidade temporal e Coloração de grafos · Veja mais »
Complexidade computacional
A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si.
Novo!!: Complexidade temporal e Complexidade computacional · Veja mais »
Complexidade de caso médio
Em teoria de complexidade computacional, a complexidade de caso médio de um algoritmo é a quantidade de algum recurso computacional (tipicamente tempo) utilizado pelo algoritmo, numa média sobre todas as entradas possíveis.
Novo!!: Complexidade temporal e Complexidade de caso médio · Veja mais »
Complexidade de pior caso
Na Ciência da computação a “Complexidade de pior caso” (usualmente denotada em notação assintótica) mede os recursos (ex. tempo de execução, memória) que um algoritmo precisa no pior caso.
Novo!!: Complexidade temporal e Complexidade de pior caso · Veja mais »
Computação paralela
Computação paralela é uma forma de computação em que vários cálculos são realizados ao mesmo tempo, operando sob o princípio de que grandes problemas geralmente podem ser divididos em problemas menores, que então são resolvidos concorrentemente (em paralelo).
Novo!!: Complexidade temporal e Computação paralela · Veja mais »
Conjunto de instruções
Conjunto de instruções (tradução de instruction set) são as operações que um processador, microprocessador, microcontrolador, CPU ou outros periféricos programáveis suporta, fornece ou disponibiliza para o programador, ou seja, é a representação em mnemônicos do código de máquina, com a finalidade de facilitar o acesso ao componente.
Novo!!: Complexidade temporal e Conjunto de instruções · Veja mais »
Correlação parcial
Em teoria das probabilidades e estatística, a correlação parcial mede o grau de associação entre duas variáveis aleatórias, com o efeito de um conjunto de variáveis aleatórias de controle removido.
Novo!!: Complexidade temporal e Correlação parcial · Veja mais »
DLOGTIME
DLOGTIME é a classe de complexidade de todos problemas computacionais solúveis em uma quantidade logarítimica de tempo computacionais por uma máquina de Turing determinística.
Novo!!: Complexidade temporal e DLOGTIME · Veja mais »
Exptime
Na teoria da complexidade computacional, a classe de complexidade Exptime (às vezes chamado EXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em O(2p(n)) tempo, onde p (n) é uma função polinomial de n. Em termos de DTIME, Sabemos que e também, pelo time hierarchy theoremeo space hierarchy theorem, que assim pelo menos uma das três primeiras inclusões e pelo menos uma das três últimas inclusões deve ser adequada, mas não se sabe quais são.
Novo!!: Complexidade temporal e Exptime · Veja mais »
Fatoração de inteiros
Na teoria dos números, a fatoração de inteiros é a decomposição de um número composto em um produto de números inteiros menores.
Novo!!: Complexidade temporal e Fatoração de inteiros · Veja mais »
Função de Ackermann
Na teoria da computabilidade, a Função de Ackermann, nomeada por Wilhelm Ackermann, é um dos mais simples e recém-descobertos exemplos de uma função computável que não são funções recursivas primitivas.
Novo!!: Complexidade temporal e Função de Ackermann · Veja mais »
Função polinomial
Gráfico de uma função polinomial Em matemática, função polinomial é uma função P que pode ser expressa da forma: em que n é um número inteiro não negativo e os números a_0, a_1,...
Novo!!: Complexidade temporal e Função polinomial · Veja mais »
Grande-O
''g''(''x'') sempre que ''x'' ≥ ''x''0. Na matemática, a notação O-grande descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples.
Novo!!: Complexidade temporal e Grande-O · Veja mais »
Heapsort
O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção.
Novo!!: Complexidade temporal e Heapsort · Veja mais »
Identidades logarítmicas
Em matemática, existem diversas identidades logarítmicas.
Novo!!: Complexidade temporal e Identidades logarítmicas · Veja mais »
Insertion sort
thumb Insertion Sort, ou ordenação por inserção, é um algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez.
Novo!!: Complexidade temporal e Insertion sort · Veja mais »
Intro sort
Introsort ou introspective sort é um algoritmo de ordenação criado por David Musser em 1997.
Novo!!: Complexidade temporal e Intro sort · Veja mais »
László Babai
László (Laci) Babai (Budapeste) é um matemático e cientista da computação húngaro.
Novo!!: Complexidade temporal e László Babai · Veja mais »
László Lovász
László Lovász (Budapeste) é um matemático húngaro, mais conhecido por seu trabalho em combinatória, pelo qual recebeu o Prêmio Wolf de Matemática e o Prêmio Knuth em 1999.
Novo!!: Complexidade temporal e László Lovász · Veja mais »
Limitantes superiores e inferiores
Em Matemática especialmente em Teoria da ordem, o limitante superior (cota superior em Análise Real) de um Subconjunto de um Conjunto parcialmente ordenado (K, ≤) é um elemento de K que é maior ou igual de cada elemento de S. O termo limitante inferior é definido dubiamente como um elemento de K que é menor ou igual de cada elemento de S. Um conjunto com o limite superior é dito limitado por cima por aquele limite, um conjunto com um limite inferior é dito limitado inferiormente para conjuntos que tem limites superior (respectivamente inferior). .
Novo!!: Complexidade temporal e Limitantes superiores e inferiores · Veja mais »
Logaritmo
urlmorta.
Novo!!: Complexidade temporal e Logaritmo · Veja mais »
Logaritmo iterado
O termo logaritmo iterado refere-se, em termos bilogicos, a uma função definida pela aplicação repetida (iterada) da função logaritmo sobre seu argumento.
Novo!!: Complexidade temporal e Logaritmo iterado · Veja mais »
Merge sort
O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação por comparação do tipo dividir-para-conquistar.
Novo!!: Complexidade temporal e Merge sort · Veja mais »
Michael Sipser
Michael Fredric Sipser é um professor de Matemática Aplicada no grupo de teoria da computação do Massachusetts Institute of Technology.
Novo!!: Complexidade temporal e Michael Sipser · Veja mais »
Modelo de computação
Em teoria da computabilidade, um modelo de computação é a definição de um conjunto de operações que podem ser usadas numa computação e seus respectivos custos.
Novo!!: Complexidade temporal e Modelo de computação · Veja mais »
Ordenação por comparação
Um algoritmo de comparação é um tipo de algoritmo de ordenação que lê apenas os elementos da lista através de uma operação de comparação abstrata única (muitas vezes um operador "menor ou igual a"), que determina qual dos dois elementos devem ocorrer em primeiro lugar na lista final de classificação.
Novo!!: Complexidade temporal e Ordenação por comparação · Veja mais »
Otimização
máximo global em (''x, y, z'').
Novo!!: Complexidade temporal e Otimização · Veja mais »
P (complexidade)
Na teoria da complexidade computacional, P é o acrônimo em inglês para Tempo polinomial determinístico (Deterministic Polynomial time) que denota o conjunto de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística.
Novo!!: Complexidade temporal e P (complexidade) · Veja mais »
Pesquisa binária
A pesquisa ou busca binária (em inglês binary search algorithm ou binary chop) é um algoritmo de busca em vetores que segue o paradigma de divisão e conquista.
Novo!!: Complexidade temporal e Pesquisa binária · Veja mais »
Problema de decisão
Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não.
Novo!!: Complexidade temporal e Problema de decisão · Veja mais »
Problema de isomorfismo de grafos
O problema de isomorfismo de grafos é um problema computacional para determinar se dois grafos finitos são isomórficos.
Novo!!: Complexidade temporal e Problema de isomorfismo de grafos · Veja mais »
Problema do caixeiro-viajante
O problema do caixeiro-viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem.
Novo!!: Complexidade temporal e Problema do caixeiro-viajante · Veja mais »
Programação dinâmica
Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória.
Novo!!: Complexidade temporal e Programação dinâmica · Veja mais »
Programação linear
Exemplo de poliedro (bidimensional) resultante das condições de um problema de programação linear. Em matemática, problemas de Programação Linear (PL) são problemas de optimização nos quais a função objetivo e as restrições são todas lineares.
Novo!!: Complexidade temporal e Programação linear · Veja mais »
Quicksort
O algoritmo quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscovo como estudante.
Novo!!: Complexidade temporal e Quicksort · Veja mais »
Sistema de numeração binário
O sistema binário ou de base 2 é um sistema de numeração posicional em que todas as quantidades se representam com base em dois números, ou seja, zero e um (0 e 1).
Novo!!: Complexidade temporal e Sistema de numeração binário · Veja mais »
Smoothsort
Algoritmo de ordenação relativamente simples.
Novo!!: Complexidade temporal e Smoothsort · Veja mais »
Teorema da convolução
Em matemática, o teorema da convolução estabelece que, sob condições apropriadas, a transformada de Fourier de uma convolução de duas funções absolutamente integráveis é igual ao produto ponto a ponto das transformadas de Fourier de cada função.
Novo!!: Complexidade temporal e Teorema da convolução · Veja mais »
Teoria dos grafos
Grafo com quatro vértices e 6 arestas. É um grafo completo, conexo e planar. A teoria dos grafos ou de grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.
Novo!!: Complexidade temporal e Teoria dos grafos · Veja mais »
Tese de Cobham
A Tese de Cobham, também conhecida como a tese de Cobham–Edmonds (assim denominada em referência a Alan Cobham e Jack Edmonds), assegura que problemas computacionais podem ser resolvidos de maneira viável em algum dispositivo de computação apenas se forem computáveis em tempo polinomial, ou seja, se pertencerem à classe de complexidade P.
Novo!!: Complexidade temporal e Tese de Cobham · Veja mais »
Teste de primalidade AKS
O teste da primalidade AKS (também conhecido como teste da primalidade Agrawal-Kayal-Saxena) é um algoritmo de teste de primalidade determinístico criado e publicado por cientistas Indianos chamados Manindra Agrawal, Neeraj Kayal e Nitin Saxena em 6 de agosto de 2002 em um trabalho intitulado "PRIMES is in P".
Novo!!: Complexidade temporal e Teste de primalidade AKS · Veja mais »
Transformada rápida de Fourier
Em matemática, engenharia e em áudio profissional, a Transformada rápida de Fourier (do inglês: Fast Fourier Transform, abreviado FFT) é um algoritmo que calcula a Transformada discreta de Fourier (DFT) e a sua inversa (Teorema inverso de Fourier), criado pelo estatístico estadunidense John Tukey. A análise de Fourier converte um sinal do domínio original para uma representação no domínio da frequência e vice-versa. De grande importância em uma vasta gama de aplicações, de Processamento digital de sinais para a resolução de equações diferenciais parciais a, algoritmos para multiplicação de grandes inteiros. A transformada é amplamente utilizadas na engenharia, ciência e matemática. As ideias básicas foram popularizadas em 1965, mas alguns algoritmos foram obtidos em 1805. Uma Transformada rápida de Fourier calcula rapidamente essas transformações fatorizando a matriz da Transformada discreta de Fourier em um produto de fatores esparsos (principalmente zero). Como resultado, ele consegue reduzir a complexidade de calcular a Transformada discreta de Fourier de O\left(N^2\right), ou seja na ordem de n elevado ao quadrado, que surge se alguém simplesmente aplica a definição de Transformada discreta de Fourier, a O(N \log N), onde N é o tamanho dos dados. Em 1994, Gilbert Strang descreveu a Transformada rápida de Fourier como "O algoritmo numérico mais importante da nossa vida", e foi incluída no Top 10 Algorithms of 20th Century pela revista IEEE Computing in Science & Engineering.
Novo!!: Complexidade temporal e Transformada rápida de Fourier · Veja mais »
União-busca
Em ciência da computação, uma estrutura de dados união-busca também chamado de estrutura de dados disjoint-set é uma estrutura de dados que mantém o controle de um conjunto de elementos particionados em subconjuntos disjuntos (não sobreposicionados).
Novo!!: Complexidade temporal e União-busca · Veja mais »
2-EXPTIME
Na teoria da Complexidade Computacional, a classe de complexidade 2-EXPTIME (também chamada 2-EXP) é o conjunto de todos os problemas de decisão solucionáveis por uma Máquina de Turing Determinística em tempo O(22p(n)), onde p(n) é uma função polinomial de n. Em termos de DTIME, Nós sabemos que: 2-EXPTIME também pode ser reformulado como a classe do espaço AEXPSPACE, os problemas que podem ser solucionados por uma Máquina de Turing Alternada em espaço exponencial.
Novo!!: Complexidade temporal e 2-EXPTIME · Veja mais »
Redireciona aqui:
Complexidade de Tempo, Tempo logarítmico.
