Todas as perguntas
Com as tags complexidade or complexidade-de-algoritmo
26 perguntas
83
votos
2
respostas
44mil
visitas
O que é a complexidade de um algoritmo?
O que é a complexidade de um algoritmo?
E quais as formas de medi-la? (Big O, Big Theta...)
35
votos
2
respostas
4mil
visitas
O que é memoization?
O que é memoization? Em quais circunstâncias pode ser útil e como utilizar? (Se possível, ilustrar com um exemplo simples)
25
votos
3
respostas
4mil
visitas
Como provar a ordem assintótica de um algoritmo?
Considerando um algoritmo como o abaixo:
function somaMatriz(matA, size) {
let soma = 0; // 1
for(let i = 0; i < size; i++){ // n + ...
4
votos
1
resposta
467
visitas
Iterar sobre duas Lista de forma otimizada - Otimização de Algoritmo O(n²) C#
Preciso iterar sobre duas lista e fazer a comparação dos valores contidos em ambas. Porém a forma que estou fazendo, está consumindo muito tempo, pois a grandeza do meu algoritmo é O(n²), seguem ...
21
votos
2
respostas
20mil
visitas
O que é um problema NP completo?
O que é um problema NP completo? Que exemplos podem ser dados para ilustrar um problema NP completo? Por que estes problemas são considerados importantes?
17
votos
1
resposta
305
visitas
Como pode a busca de um elemento em um conjunto ser O(1)?
Conforme a página oficial do Python quanto à complexidade dos algoritmos no tempo, as sequências list e set possuem as seguintes características:
List
Set
Destaque para o operador in, que verifica ...
11
votos
1
resposta
6mil
visitas
Qual a diferença entre "Big O", "Big Theta" e "Big Omega"?
Pra que serve cada um destes "Big O", "Big Theta" e "Big Omega" e quando usar cada um para descrever a complexidade de um algoritmo?
25
votos
1
resposta
1mil
visitas
Por que aprender algoritmos diferentes que resolvem o mesmo problema?
Eu não tenho treinamento em ciência da computação. Por exemplo, sempre que quero ordenar um vetor de números x em uma das linguagens de programação que utilizo, basta rodar sort(x) e tudo se resolve.
...
24
votos
1
resposta
756
visitas
O que é a classe de complexidade NPI?
Estudando sobre complexidade, me deparei com o termo NPI. Ele significa NP-intermediário. Mas não entendi o que é esse "intermediário".
O que caracteriza um problema NPI? Por que ela tem esse nome?
...
7
votos
3
respostas
2mil
visitas
Ordenar lista encadeada com método O(n*log(n))
Eu preciso ordenar uma lista encadeada (implementação própria, sem utilizar API do Java) com um método de ordenação que possua complexidade O(n*log(n)). Pesquisando métodos que satisfaçam a condição ...
5
votos
1
resposta
405
visitas
Análise de Complexidade de Algoritmo
Um professor da minha faculdade passou um exercício para analisar a complexidade temporal desse algoritmo, mas eu não estou conseguindo de jeito nenhum. Alguém sabe me dar uma luz de como separar o ...
2
votos
1
resposta
227
visitas
Existe algum algoritmo de ordenação que execute realmente em O(n)?
Se tal algoritmo existe, como é possível um algoritmo ordenar uma coleção de dados em tempo linear mesmo caindo no pior caso possível (invertido)?
14
votos
3
respostas
5mil
visitas
Como medir a complexidade de um algoritmo?
Eu preciso saber se meu algoritmo atende a demanda do seguinte enunciado:
Implemente um algoritmo com complexidade O(n) que realize o fatorial
de um número x tal que x pertence aos Naturais.
#...
8
votos
3
respostas
278
visitas
Dois parâmetros diferentes que uma função aceita podem classificá-la como tendo complexidade O(n²)?
Digamos que eu defina uma função da seguinte forma, que aceite um argumento a que seja um array bidimensional de números:
function totalSum(a) {
let total = 0;
for (const elem of a) {
for (...
7
votos
2
respostas
2mil
visitas
Bogosort - o que é isto?
O que faz exatamente o algoritmo de ordenação bogosort?
Por que muitos dizem que ele é ineficiente?
6
votos
1
resposta
577
visitas
Algoritmo O(n log n) para identificar intervalos contíguos dada uma lista de intervalos
Tenho o seguinte problema: Dada uma lista com n intervalos contínuos, retorne uma lista de m intervalos contínuos tal que:
todo ponto da lista de entrada esteja contido em algum dos intervalos da ...
4
votos
1
resposta
7mil
visitas
O que é o teorema mestre (master theorem)?
O que é o teorema mestre (master theorem)? Qual sua importância na análise de complexidade de algoritmos?
3
votos
1
resposta
596
visitas
Complexidade temporal de algoritmo palíndromo recursivo
Preciso analisar o consumo de tempo do meu algoritmo, para um vetor de tamanho n = f - i + 1, através de uma recursão, para então definir uma formula fechada.
public class ehpalindromo {
public ...
3
votos
1
resposta
1mil
visitas
Definição Notação "Little-O" ( Pequeno O)
Gostaria de entender um pouco melhor sobre a Notação Little-O, é para fins acadêmicos, porem não tenho encontrado conteúdo suficiente ou de uma forma um pouco mais "clara", para entendimento. Estou um ...
3
votos
2
respostas
6mil
visitas
lista, max/min em python
Olá, preciso fazer um algoritmo em python que leia um arquivo de texto .csv que contém literalmente 5 milhões de números e preciso que esse algoritmo me diga qual é o menor e qual é o maior número da ...
3
votos
2
respostas
2mil
visitas
Como obter o tempo do sistema operacional em nanosegundos ou milisegundos utilizando o Qt Creator?
Como posso obter o tempo do sistema em nanosegundos ou milisegundos em C++ utilizando o Qt Creator?
Por exemplo, em Java uso:
long tempoInicial = System.nanoTime();
treinaRNAEpocas(10000);
long ...
2
votos
1
resposta
88
visitas
As configurações de hardware são relevantes para a medição da eficiência dos algoritmos de ordenação?
Eu estava lendo um artigo no DevMedia sobre os principais algoritmos de ordenação.
No artigo são comparados quatro algoritmos desse tipo, bubble sort, selection sort, quick sort e insertion sort.
...
1
voto
1
resposta
96
visitas
Consumo de tempo em código cúbico
Preciso calcular o consumo de tempo do seguinte algoritmo:
int somaSequencial(int v[],int n){
int m = 0;
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
int ...
1
voto
2
respostas
350
visitas
Dúvida em Complexidade de Algoritmos
Estou com uma dúvida em Complexidade de Algoritmos. Como podem ver, na imagem abaixo, as expressões são equivalentes, ou seja, possuem as mesmas qualidades e o mesmo termo dominante (n²), então porque ...
0
votos
1
resposta
894
visitas
Qual a complexidade do algoritmo?
Estou aprendendo a calcular a complexidade de algoritmos, usando a notação Big-O, porém estou com dificuldades no algoritmo abaixo:
a=0
for(int i = n; i>0; i -=2){
for(int j = i+1; j<=n;j+=...
0
votos
1
resposta
1mil
visitas
Qual a complexidade de cada uma dessas funções?
Lista circular simples implementada em C
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct s_no{
float info;
struct s_no* proximo;
} no_t;
no_t* ...