Todas as perguntas
Com as tags complexidade or complexidade-de-algoritmo
86 perguntas
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 ...
-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 ...
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 ...
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 ...
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 ...
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 ...
-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 ...
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 ...
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 ...
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 ...
-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&...
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 ...
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):
...
-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 < ...
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)...
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 = ...
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)):
...
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 (...
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?
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?
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, ...
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) ...
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
...
-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 '...
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'...
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+=...
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(...
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 ...
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 ...
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.
...
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 ...
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 ...
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 &...
-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 ...
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 ...
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 ...
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 ...
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á ...
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(...
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 ...
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 ...
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 ...
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?
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á ...
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?
...
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++)
...
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;
}
}
...
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,...
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 ...
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)?