Skip to main content

Todas as perguntas

Filtrar por
Ordenado por
Com tags
0 votos
1 resposta
126 visitas

O que é exatamente complexidade de tempo? [duplicada]

Estava lendo a respeito de buffer circular e sua implementação e me deparei com o termo complexidade de tempo ( no caso, o texto afirma que o buffer circular tem complexidade O (1) ). Pelo que li a ...
Gabriel Oliveira's user avatar
-1 votos
2 respostas
135 visitas

O que o computador faz com 2 valores distintos que precisam ser retornados e estão no mesmo escopo de memória? [fechada]

Possuo esse código com essa única função, ela realiza o produto entre 'a' e 'b' que recebe da função "main". Gostaria de saber como a função contida nesse código lida com o retorno de 2 ...
Ricardo Farias's user avatar
1 voto
0 respostas
134 visitas

Complexidade do algoritmo strand sort

Estou utilizando o strand sort para fazer um trabalho da faculdade e queria saber se em nível de complexidade, em pior caso ele O(n^2). e eu queria saber em qual circunstancia seria melhor utilizar ...
Luyza's user avatar
  • 51
0 votos
1 resposta
159 visitas

Análise assintótica do melhor e pior caso

Quero saber qual seria o melhor e pior caso do meu código. Ainda não entendo muito bem como fazer esses tipos de análise em um código e queria ter alguma ajuda para saber como identificar. Eu entendo ...
fusionhelhotmailcom's user avatar
1 voto
1 resposta
73 visitas

Complexidade assintótica de função

Quando eu tenho uma função de duas variáveis como: f(x, y) = log y + 3 * x^4 Posso dizer que o domínio assintótica da função é theta(x^4)? Ou eu tenho que considerar as duas variáveis e definir como ...
jackkunk's user avatar
1 voto
1 resposta
96 visitas

Grau de complexidade

def fRecursivo(n): if(n == 0 ): return 1 if (n%2 ==1): return (n+3*fRecursivo(n-1)) if(n%2 == 0 and n> 0): return (n+n+3*n*fRecursivo(n-1)) Qual o grau de ...
Davi Henrique's user avatar
-1 votos
1 resposta
195 visitas

Como provar a complexidade de um algoritmo?

Eu tenho algumas questões sobre analisar complexidade de algoritmo, eu tenho a resposta correta delas(verdadeiro ou falsa),porém não sei como provar, se alguém conseguir me explicar o raciocínio pra ...
Fernando's user avatar
1 voto
1 resposta
439 visitas

Como posso diminuir o nível de complexidade dessa função?

Estou aprendendo desenvolvimento Web com HTML, CSS e JavaScript e me deparei com o problema de gerar um número de telefone com parêntese, traço e espaço. Como estou começando desenvolvi um código que ...
Rogério Rodrigues Sousa's user avatar
4 votos
1 resposta
4mil visitas

Melhor algoritmo de ordenação em pior caso

Quero saber qual algoritmo tem o melhor desempenho ao lidar com seu pior caso comparado a outros lidando cada um com o seu próprio pior caso, todos aplicados em ordenação de array. Para entender ...
RHER WOLF's user avatar
  • 1.586
0 votos
1 resposta
65 visitas

Qual é a coplexidade de minha solução?

Tenho o seguinte problema de computação: Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M). More formally check if there ...
Vinicius Morais's user avatar
-1 votos
2 respostas
162 visitas

Qual a real complexidade por traz do Sleep Sort em comparação aos demais?

Sei que esta é a minha primeira pergunta aqui no stackoverflow em português. No entanto senti a falta de menção a este algoritmo chamado sleep-sort. Pelo que sei a origem dele é "supostamente&...
Matheus C. França's user avatar
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 ...
Jefferson Quesado's user avatar
0 votos
1 resposta
433 visitas

Como Diminuir complexidade de uma função com dois Loops em Python

Essa função retorna o número de pares em que A[i] > A[j] para 1 < i < j < n def calc(A): cont = i = j = 0 while i < len(A): j = i + 1 while j < len(A): ...
Pirategull's user avatar
-1 votos
1 resposta
101 visitas

Complexidade de algoritmo de dois laços

Qual seria a função de complexidade e o Big O do código abaixo? int[] alg4(int[] arr1, int[] arr2) { int i = 0; int j = 0; int[] arr3 = new int[arr1.Length+arr2.Length]; for (i = 0; i < ...
Wernen Rodrigues's user avatar
3 votos
0 respostas
54 visitas

Noção Big O e small O, Big Omega e Small Omega, aplicado a funções exponenciais muito parecidas

No livro acadêmico que utilizamos, pede para relacionarmos o que uma função A é de uma função B (ex: A = O(B)) Tem uma relação que não consigo entender a resolução da resposta A = (1,21)^n B = (1,2)...
Pirategull's user avatar
7 votos
1 resposta
2mil visitas

O que é um algoritmo Ótimo?

Estou tendo aulas de Introdução a Analise de Complexidade. Me foi dito que um exemplo de um algoritmo ótimo é o algoritmo para achar o menor valor entre elementos de um array de inteiros: int min = ...
water's user avatar
  • 981
7 votos
2 respostas
1mil visitas

Complexidade de algoritmo em Python com dois loops

Esse algorítimo serve pra retornar o elemento que mais se repete numa lista: def algorithm_x(a): x = 0 y = 0 for i in range(0, len(a)): k = 1 for j in range(i+1, len(a)): ...
Pirategull's user avatar
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 (...
Luiz Felipe's user avatar
  • 36,5mil
6 votos
1 resposta
118 visitas

Dúvida em análise de algoritmos

Estou com dificuldades para conseguir provar se f(n)=Omega(g(n)), então g(n) = O(f(n)). Como seria essa comprovação? Com cálculo e com teoria?
Ana Caroline's user avatar
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?
Lucas Emanuel's user avatar
0 votos
2 respostas
626 visitas

Algoritmo para soma de duplas

Dado um vetor V de inteiros, ordenado, e um valor s, escrever um algoritmo de complexidade O(n) para calcular quantos pares de números têm soma s. Neste vetor poderá haver números repetidos. Note que, ...
Bakun's user avatar
  • 21
1 voto
1 resposta
53 visitas

Complexidade de algorítimo simples

estou tendo dificuldade nesse exercício de complexidade de algorítimos, alguém pode dar uma luz? Provar que, se f(n) = -n então f(n) é O(1). Uma ideia que tive foi que para qualquer n positivo, f(n) ...
Bakun's user avatar
  • 21
8 votos
1 resposta
805 visitas

Tempo de execução de um algoritmo

def isprime(n): # 0 and 1 are not prime if n < 2: return False # 2 is prime if n == 2: return True # even numbers are not prime if n % 2 == 0: return False ...
mayconrralves's user avatar
-3 votos
3 respostas
274 visitas

Qual problema com o algoritmo Bubble Sort?

Estou criando um código com o algoritmo Bubble Sort, porém ao compilar eu recebo errors, os quais são: In function 'int main()': 16 33 [Error] cannot convert 'int*' to 'int**' for argument '...
rebel_vitor's user avatar
6 votos
1 resposta
521 visitas

Um dicionário Python é tão eficiente quanto uma árvore ou um hash?

Eu uso muito dicionários em Python: dic = dict() #ou dic = {} dic['113654'] = {'nome': 'João', 'idade': 21} dic['853872'] = {'nome': 'Maria', 'idade': 27} dic['427845'] = {'nome': 'Fernando', 'idade'...
Jônatas Trabuco Belotti's user avatar
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+=...
Erik Jhonatta's user avatar
4 votos
1 resposta
1mil visitas

Calculo de complexidade BubbleSort

Gostaria de saber como posso demonstrar por indução de cálculo a complexidade do algoritmo bubblesort, tanto no melhor caso, quanto no pior caso. def bubble_Sort(alist): for numc in range(len(...
Mauricio's user avatar
0 votos
1 resposta
261 visitas

Busca Binaria - complexidade

Boa Tarde, alguém poderia me ajudar com a disciplina de complexidade de algoritmo, to parado na questão de busca binaria. Algum pode me ajudar com a questão abaixo: Considere novamente outra variação ...
Marcio Ferreira's user avatar
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 ...
Isabella Rosa's user avatar
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. ...
Marcus Nunes's user avatar
  • 19mil
0 votos
2 respostas
153 visitas

Sobre Análise de Algoritmos [fechada]

Tô com uma dúvida em duas questões a respeito do conteúdo de análise algoritmos. Questões Em ciência da computação, um algoritmo é uma sequência finita de ações executáveis que visam obter uma ...
Igor Alisson's user avatar
0 votos
2 respostas
270 visitas

Calculo do T(n) [fechada]

Alguém poderia me explicar como se calcula o T(n) desse algoritmo sendo n >= 0? Já vi vídeos e aulas e não estou conseguindo entender como funciona esse cálculo. T(n) de um algoritmo é o quanto de ...
Brenda Xavier's user avatar
0 votos
1 resposta
1mil visitas

Função de complexidade

Estou com dúvidas de como fazer uma análise de função de complexidade desse código Java package exercicio_2_ed; public class Potencias { public void calcular( int[] numeros ){ for( int i = 0; i &...
Vinnicius Gomes's user avatar
-1 votos
1 resposta
160 visitas

Projeto de algoritmos por divisão e conquista

Preciso projetar esse algoritmo utilizando o paradigma de divisão e conquista (indução forte). Não estou conseguindo sair do lugar... Sejam A e B dois vetores de números inteiros tais que o número ...
Luiz Felipe Raveduti Zafiro's user avatar
4 votos
1 resposta
1mil visitas

Quando e onde usar os termos: complexidade de tempo, complexidade de espaço?

Estou usando o livro estruturas de Dados: Algoritmos, Análise da Complexidade e Implementações em JAVA e C/C++ pois ele ajuda com exemplos práticos de implementação. No capitulo 1 tem o seguinte ...
Ronaldo Melo's user avatar
2 votos
1 resposta
376 visitas

Como ordenar um array pela frequência de aparição de cada elemento?

Para não delongar demais vou direto ao ponto, estou tentando fazer um programa para um exercício que possuí a seguinte instrução: Construa uma função int ordenaFreq(int v[], int n) eficiente, isto ...
Vinícius's user avatar
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 ...
Igor Ribeiro's user avatar
1 voto
1 resposta
46 visitas

Ordenando Com determinada condição

Fiz a questão Quem Vai Ser Reprovado? que tinha a regra Os alunos seriam ordenados conforme o número de problemas resolvidos, com empates resolvidos de acordo com a ordem alfabética dos nomes (não há ...
rafael marques's user avatar
2 votos
1 resposta
327 visitas

Quicksort vs Radix-sort

Eu gostaria de saber o porque Quicksort é mais difuso do que Radix-sort. Uma vez que o quicksort usa como base para o ordenamento a comparação e radix-sort não o segundo pode ser mais rápido que O(...
Um Programador's user avatar
0 votos
1 resposta
78 visitas

Quantidade de co-ocorrencias em uma matriz

Tenho uma duvida mais matemática do que computacional. Supomos que temos uma matriz quadrada M de dimensão n², onde n é qualquer inteiro maior que zero. Percorrendo essa matriz, atribuindo j como ...
Francisco Sobrinho's user avatar
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 ...
Woss's user avatar
  • 77,2mil
2 votos
1 resposta
555 visitas

Eliminar ciclos em grafo removendo menos vértices

Gostaria de saber se alguém sabe se é possível eliminar todos os ciclos de um grafo não-direcionado (n vértices) sem pesos, removendo o menor número de vértices, em tempo O(n²)? Obs: O grafo pode ...
HiHello's user avatar
  • 792
3 votos
1 resposta
691 visitas

Complexidade de algoritmos - Notação Big O

A função f(n) = n3 + 2 domina assintoticamente a função g(n) = 200n2 + 5, para um valor de n suficientemente grande. Ou seja, g(n) é O(f(n)) Como posso provar que essa afirmação é verdadeira?
thaismota17's user avatar
3 votos
1 resposta
2mil visitas

Notação Big O - Complexidade O(log n)

Tenho algumas perguntas acerca dessa complexidade, qual base é usada nesse logaritmo, 2 ou 10? e por quê? Buscando no google vi alguns comentários falando que a base não importava.. O logaritmo está ...
Strawberry Swing's user avatar
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? ...
Jefferson Quesado's user avatar
2 votos
1 resposta
287 visitas

Ordem Crescimento

Necessitava de ajuda para perceber qual o cálculo correto da ordem de crescimento deste excerto de código (função de N=2^M) int sum=0; for (int i = 0; i < = N; i++) for(j = 1; j <= N; j++) ...
João's user avatar
  • 109
1 voto
1 resposta
709 visitas

Qual código tem um custo maior? (Bubblesort em C)

void bubblesort(int *A, int n) { int i, aux; for(i=0; i<n-1; i++){ if(A[i]>A[i+1]){ aux = A[i]; A[i] = A[i+1]; A[i+1] = aux; } } ...
Hatus Daniel's user avatar
2 votos
1 resposta
162 visitas

Este código é O(n)?

#include <stdlib.h> #include <time.h> int maior(int n, int A[]){ if(n==1) return A[0]; if(maior(n-1, A)<A[n-1]) return A[n-1]; else return maior(n-1,...
Hatus Daniel's user avatar
14 votos
2 respostas
1mil visitas

Problema dos Generais Bizantinos. Como implementar uma solução?

Considerações iniciais Estou realizando uma pesquisa sobre Bitcoin e esbarrei no conceito do Problema dos Generais Bizantinos, onde o criador do Bitcoin - Satoshi Nakamoto - escreveu "Bitcoin: A ...
pss1suporte's user avatar
  • 1.637
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)?
flpn's user avatar
  • 629