A notação big-O não descreve o tempo exato que um algoritmo leva, mas apenas indica um tempo de execução dentro de um fator constante. É uma forma de comparar algoritmos.
Acho que porque na lista só existe um número 1, para fazer 11 teriam que ter dois. Ele é apenas um rearranjo dos números do conjunto seguindo alguma regra, acho eu
Sobre a parte da memória eu fiquei com uma dúvida. Eu tenho um array de 10 items e quero achar 1. Pelo que você falou, eu só preciso alocar um espaço de memória, que seria o espaço desse item buscado. Mas eu n preciso alocar um espaço pro array inteiro? Tipo, assumindo que esse array está salvo num arquivo que é lido pelo programa, conforme o programa lê o arquivo ele não aloca espaço na memória pros dados lidos? Talvez isso mostre minha falta de conhecimento sobre a execução de um programa, mas eu assumo que sim e que esse espaço vai crescer conforme o arquivo lido. Ou ele vai deletando o "histórico" de dados já lidos conforme ele progride pela leitura? Tipo li as 5 primeiras posições, quando eu vou ler a 6ª, deleto a 1ª e por aí vai.
nesse caso do O(1) seria uma situação onde esse input seja a posição do array, entao ele nao precisa percorrer o array Seria algo do tipo void main() { final List frutas = ['maçã', 'banana', 'laranja']; final String segundaFruta = frutas[1]; print(segundaFruta); // Tempo de execução: O(1) }
O array (input) já está na memória, veio de algum lugar: o usuário digitou, um arquivo foi lido... qualquer coisa do tipo. O espaço alocado se refere ao output do algoritimo - quanta memória você precisa alocar pra executar todos os passos do algoritimo e gerar um resultado.
assisti 3 vezes agora que eu entendi. obrigado
Show demais. Muito bom.
Suas explicações são excelentes.
Excelente explicação!
Muito bom, eu sempre tento lembrar das curvas de cada função para saber qual é a pior/melhor em tempo
Muito interessante fazer esses desenhos Augusto.
Obrigado.
ajudou pra caralho.
Cara obrigado pelo vídeo, sou iniciante nos estudos de programação e to mesclando essa parte conceitual com estudos práticos.
curti mt mosntro
A notação big-O não descreve o tempo exato que um algoritmo leva, mas apenas indica um tempo de execução dentro de um fator constante. É uma forma de comparar algoritmos.
Excelente explicação ajuda bastante quem está estudando estrutura de dados por livro (o que é o meu caso).
Boa explicação.
massa
Tava pensando em estudar mais afundo isso, vc tem indicações bibliográficas para estudar esses algoritmos e estrutura de dados ?
Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos
No O(n!) com array 1 2 eu não teria as permutações 11 e 22 ? Ou só considero com elementos diferentes?
Acho que porque na lista só existe um número 1, para fazer 11 teriam que ter dois. Ele é apenas um rearranjo dos números do conjunto seguindo alguma regra, acho eu
Sobre a parte da memória eu fiquei com uma dúvida.
Eu tenho um array de 10 items e quero achar 1. Pelo que você falou, eu só preciso alocar um espaço de memória, que seria o espaço desse item buscado. Mas eu n preciso alocar um espaço pro array inteiro? Tipo, assumindo que esse array está salvo num arquivo que é lido pelo programa, conforme o programa lê o arquivo ele não aloca espaço na memória pros dados lidos? Talvez isso mostre minha falta de conhecimento sobre a execução de um programa, mas eu assumo que sim e que esse espaço vai crescer conforme o arquivo lido.
Ou ele vai deletando o "histórico" de dados já lidos conforme ele progride pela leitura? Tipo li as 5 primeiras posições, quando eu vou ler a 6ª, deleto a 1ª e por aí vai.
nesse caso do O(1) seria uma situação onde esse input seja a posição do array, entao ele nao precisa percorrer o array
Seria algo do tipo
void main() {
final List frutas = ['maçã', 'banana', 'laranja'];
final String segundaFruta = frutas[1];
print(segundaFruta);
// Tempo de execução: O(1)
}
O array (input) já está na memória, veio de algum lugar: o usuário digitou, um arquivo foi lido... qualquer coisa do tipo. O espaço alocado se refere ao output do algoritimo - quanta memória você precisa alocar pra executar todos os passos do algoritimo e gerar um resultado.
o espaço da memória é referente apenas a quantidade que o algoritmo vai alocar, com variaveis de retorno e afins