Projeto e Análise de Algoritmos - Aula 01 - Introdução ao projeto e análise de algoritmos

00:27:07
https://www.youtube.com/watch?v=186lPQE-h64

Summary

TLDRA aula de análise de algoritmos introduz conceitos essenciais, como definição de algoritmo, problemas, instâncias, correção de algoritmos e medição de consumo de tempo. O objetivo é entender a estrutura e o comportamento dos algoritmos antes de sua implementação, usando exemplos como ordenação e busca de caminhos mínimos. As técnicas de prova de correção são discutidas, assim como a importância de medir o tempo de execução e a complexidade computacional, introduzindo notações como Big O, para avaliar a eficiência de soluções algorítmicas.

Takeaways

  • 📝 O que é um algoritmo? Um procedimento bem definido que produz saídas a partir de entradas.
  • 🔍 A definição de um problema envolve descrever suas entradas e saídas esperadas.
  • ✅ A correção de um algoritmo é crucial: deve resolver o problema para todas as instâncias e terminar em um tempo finito.
  • 📏 Medir o tempo de execução é essencial para avaliar a eficiência de um algoritmo.
  • ⚙️ O algoritmo de ordenação por inserção é um exemplo prático de como funcionam algoritmos.
  • 🔄 Para provar a correção de um algoritmo recursivo, usa-se indução matemática.
  • 🚀 A análise de complexidade é importante na engenharia da computação para prever o comportamento de algoritmos.
  • 📊 Notações como Big O ajudam a descrever a eficiência de algoritmos em relação ao tamanho da entrada.

Timeline

  • 00:00:00 - 00:05:00

    Aula introdutória sobre análise de algoritmos e conceitos fundamentais. Definições de algoritmo, problema e instância, com exemplos práticos de problemas como ordenação e caminho mínimo, enfatizando a importância da previsão do comportamento de algoritmos antes da implementação.

  • 00:05:00 - 00:10:00

    Definição de correção de algoritmos, destacando a necessidade de um algoritmo finalizar em um tempo finito e produzir saídas corretas. Introdução da técnica de invariantes de laços e indução matemática como métodos para provar a correção de algoritmos, com exemplos práticos de um algoritmo recursivo para encontrar o máximo em um vetor.

  • 00:10:00 - 00:15:00

    Etapas para calcular o tempo e recursos necessários para resolver uma instância de problema, comparando experimentalmente diferentes algoritmos que resolvem a mesma tarefa. Demonstração da eficiência de um algoritmo de ordenação por inserção com exemplos de como ele organiza elementos e a complexidade das operações realizadas.

  • 00:15:00 - 00:20:00

    Análise detalhada do algoritmo de ordenação por inserção, ilustrando como elementos são comparados e movidos durante o processo de inserção. Discussão sobre o número de comparações feitas e impactos no desempenho em diferentes cenários, como o pior caso e melhor caso.

  • 00:20:00 - 00:27:07

    Introdução à análise empírica dos algoritmos, incluindo o consumo de recursos e tempo de execução. Discussão sobre como medir e estimar a complexidade de tempo e espaço, mencionando diferentes notações assintóticas a serem abordadas nas próximas aulas.

Show more

Mind Map

Video Q&A

  • O que é um algoritmo?

    Um algoritmo é um procedimento computacional bem definido que recebe valores como entrada e produz valores como saída.

  • O que é um problema em computação?

    Um problema é definido por uma descrição que inclui parâmetros de entrada e saída.

  • Como se determina a correção de um algoritmo?

    Um algoritmo é considerado correto se resolve o problema para toda instância de entrada e termina em um tempo finito.

  • Quais são as técnicas para provar a correção de um algoritmo?

    Para algoritmos interativos, utiliza-se a técnica de invariante de laços; para algoritmos recursivos, aplica-se a indução matemática.

  • Como é medido o consumo de tempo de um algoritmo?

    O consumo de tempo pode ser estimado experimentalmente, medindo os horários de início e fim da execução de um algoritmo.

  • O que é a notação Big O?

    A notação Big O é utilizada para descrever a complexidade computacional de um algoritmo em relação ao tamanho da entrada.

  • Qual é a importância de analisar o tempo de execução de um algoritmo?

    Analisar o tempo de execução ajuda a prever a eficiência de um algoritmo, especialmente para entradas grandes.

  • O que é um exemplo de um algoritmo comum?

    Um exemplo é o algoritmo de ordenação por inserção.

  • Como funciona um algoritmo de ordenação por inserção?

    O algoritmo percorre um vetor e insere elementos na posição correta, empurrando elementos maiores.

View more video summaries

Get instant access to free YouTube video summaries powered by AI!
Subtitles
es
Auto Scroll:
  • 00:00:00
    [Música]
  • 00:00:15
    Hola pesoal sean benvidos a nosa primera
  • 00:00:18
    aula de análisis proyecto y análisis de
  • 00:00:21
    algoritmos n Esa primera aula vamos a
  • 00:00:24
    presentar algunos conceptos
  • 00:00:25
    introductorios para
  • 00:00:28
    disciplina
  • 00:00:30
    apres presentaremos algun conitos como
  • 00:00:32
    que algoritmo o que que un problema o
  • 00:00:35
    que una instancia y apr presentaremos
  • 00:00:38
    también comoera de correción de
  • 00:00:40
    algoritmo y como medir consumo de tiempo
  • 00:00:44
    de un
  • 00:00:46
    algoritmo así como acontece con engeros
  • 00:00:49
    civ el tcnicas y algas mtricas que usan
  • 00:00:55
    para prever comportamento estruturas
  • 00:00:58
    antes de construirlas asim comoes elesen
  • 00:01:02
    nos tambén como engeros da computación a
  • 00:01:06
    gente precisa prever como que será
  • 00:01:10
    comportamento de un algoritmo antes de
  • 00:01:15
    implementarlo esa disciplina nos ayudar
  • 00:01:17
    aer exatamente ISO ent primero vamos ver
  • 00:01:20
    alguns conceitos importantes para para
  • 00:01:23
    poder traballar yer anális su algoritmos
  • 00:01:26
    primero precisamos definir o que que un
  • 00:01:29
    algoritmo un algoritmo un procedimiento
  • 00:01:32
    computacional que está bien definido que
  • 00:01:35
    recebe algun valores como entrada y
  • 00:01:38
    producir dar como resposta alg valores
  • 00:01:41
    como
  • 00:01:43
    saída otra defini simples ferr para
  • 00:01:47
    resol problemas
  • 00:01:51
    computacion un algoritmo res un problema
  • 00:01:54
    y que un problema un problema definido
  • 00:01:57
    por una descrición parámetros
  • 00:01:59
    tanto de entrada como de saída una
  • 00:02:02
    descrición sobre propriedades que a
  • 00:02:04
    resposta de
  • 00:02:06
    satisfer y o que que una instancia una
  • 00:02:09
    instancia de un problema eh se obt a
  • 00:02:13
    fixar alguns valores a fixar verdad
  • 00:02:15
    valores para todos os parmetros problema
  • 00:02:18
    de aquí a pqu vamos ver un exemplo aquí
  • 00:02:21
    temos un exemplo vamos suos un problema
  • 00:02:24
    de ordenar una secia de elementos a1 a2
  • 00:02:28
    at a
  • 00:02:30
    Y esa secia que ser ordenada de manea
  • 00:02:33
    crescente precisamos definir con que ser
  • 00:02:36
    entrada son saídas como que ser a saída
  • 00:02:40
    y cu propriedades que esa saída de
  • 00:02:43
    cumprir a entrada esa secia a1 a2 a n cu
  • 00:02:48
    que a saída a saída tamb secia a L A l a
  • 00:02:54
    L que cumpre seguintes propriedades esa
  • 00:02:58
    secia permut secia original certo
  • 00:03:02
    permuta t que a un l se menor que a do
  • 00:03:08
    L y así sucesivamente y todasas se menor
  • 00:03:13
    que a n l aquí un exemplo decia acia de
  • 00:03:18
    entrada por exemplo sera secia aquí
  • 00:03:24
    10544 y a segda sería secuencia ordenada
  • 00:03:28
    de manea crescente 4 5 10 20 40 nesta
  • 00:03:32
    disciplina vamos ver varias formas Deer
  • 00:03:36
    ISO de ordenar una secuencia de
  • 00:03:40
    elementos aquí temos un otro exemplo eh
  • 00:03:44
    de problema o problema o seguinte
  • 00:03:47
    encontrar o camino
  • 00:03:48
    mínimo desde un punto inicial at un
  • 00:03:52
    punto
  • 00:03:53
    final certo ent cualqu entrada entrada
  • 00:03:57
    entrada ser por exemplo coordenadas
  • 00:04:00
    punto inicial y coordenadas de es punto
  • 00:04:03
    final y que serda saída ser cam que mea
  • 00:04:09
    desde pto inicial atto final y al
  • 00:04:13
    propedades esam de ser
  • 00:04:17
    mínimo disciplina también vamos ver alg
  • 00:04:21
    algoritmos que per res es problema
  • 00:04:23
    problema cam mínimo por exemplo usando
  • 00:04:28
    grafos
  • 00:04:30
    cuando a gente proyet un algoritmo
  • 00:04:33
    primero queos que ver es si algoritmo
  • 00:04:35
    está correto un algoritmo correo si
  • 00:04:38
    resolve
  • 00:04:40
    problema para toda instancia de entrada
  • 00:04:43
    o algoritmo termina característica
  • 00:04:45
    importante que algoritmo termine no fi
  • 00:04:48
    infinitamente un
  • 00:04:49
    Loop intermin y produz saída que satisf
  • 00:04:54
    propiedades que for definidas para
  • 00:04:56
    problema Ah primero paso es demostrar si
  • 00:05:00
    algoritmo está correcto si f o que
  • 00:05:05
    promete para Fer a proba de correción
  • 00:05:09
    algoritmo existen algumas técnicas
  • 00:05:12
    cuando estamos trabando con un algoritmo
  • 00:05:15
    interativo que usa lazos usada a técnica
  • 00:05:19
    de invariante do lazos o que que un
  • 00:05:21
    invariante dos lazos una propriedad que
  • 00:05:24
    debe ser verdadeira antes durante y após
  • 00:05:27
    execu do lazo
  • 00:05:30
    usando ISO a gentee mostrar provar que
  • 00:05:34
    algoritmo está correto no caso de
  • 00:05:36
    algoritmos interativos no caso de
  • 00:05:38
    algoritmos
  • 00:05:41
    recursivos usada a técnica de inducción
  • 00:05:44
    matemática
  • 00:05:45
    eho instas veremos de aquí a un
  • 00:05:51
    exemplo fechamos ese exemplo de
  • 00:05:54
    algoritmo un algoritmo simples que
  • 00:05:57
    Calcula un máximo de una secuencia a
  • 00:05:59
    gente decidió un algoritmo recursivo
  • 00:06:02
    poderíamos feo un algoritmo interativo
  • 00:06:06
    también que que ent recebe como
  • 00:06:09
    parámetro un vector
  • 00:06:11
    a deo n y encontrar cu que máximo Dee
  • 00:06:17
    vector si n igual a un o se sio de
  • 00:06:21
    vector un ent ya que un máximo prio
  • 00:06:24
    elemento que único que está n vector que
  • 00:06:28
    sería caso contrario a gente Lamar
  • 00:06:32
    recursivamente algoritmo para calcular
  • 00:06:34
    que máximo vector a con n men Un
  • 00:06:38
    elementos o se desde posición un
  • 00:06:41
    posición n men ent es ese método de
  • 00:06:44
    aquí calcular que máximo desde de a
  • 00:06:49
    desde 1 n yver un valor que valor x
  • 00:06:55
    certo aquí aquí ya valor má máximo de un
  • 00:07:00
    vector de un a tn men 1 cuando obtiver
  • 00:07:05
    ese valor único que ficara para resolver
  • 00:07:07
    es perguntar si ese máximo encontrado es
  • 00:07:12
    mayor a un elemento que está faltando
  • 00:07:14
    que sería o a posición n si mayor a
  • 00:07:19
    posición n ent qui un mayor es x caso
  • 00:07:22
    contrario un mayor e a
  • 00:07:26
    de Okay ya Pro estamos o noso algoritmo
  • 00:07:31
    o próximo paso verificar se algoritmo
  • 00:07:34
    está correto estamos vendo que un
  • 00:07:36
    algoritmo recursivo ent vamos usar a
  • 00:07:40
    técnica de inducción matemática noo que
  • 00:07:43
    sería n para demostrar que algoritmo
  • 00:07:46
    está correcto ent Cómo que usamos esa
  • 00:07:49
    técnica primero falamos si algoritmo
  • 00:07:52
    está correcto para un instancia pequena
  • 00:07:54
    n ese caso para nahu después asumimos
  • 00:07:57
    para una instancia de tamaño n men
  • 00:08:00
    verificamos si está correcta y despu
  • 00:08:02
    mostramos para n
  • 00:08:04
    si que debeer ent vamos ver pasos para
  • 00:08:08
    demar cor algoritmo
  • 00:08:12
    máximo si n ig 1 Vamos ver algoritmo dev
  • 00:08:16
    a respa correta si n ig 1 sí un elemento
  • 00:08:21
    devolve a dev resposta correta
  • 00:08:26
    s por hipótesis a supor que para n mayor
  • 00:08:31
    igual a do o
  • 00:08:33
    algoritmo a llamada
  • 00:08:36
    máximo con un parámetro a y n - 1 produ
  • 00:08:39
    un resultado esperado pues n - 1 es
  • 00:08:42
    menor a n Enton supondo que esa Lía de
  • 00:08:46
    aquí Me devolve resultado correcto me
  • 00:08:49
    devolve realmente cu que máximo de
  • 00:08:53
    vector a desde posición atn - 1 tambo
  • 00:08:57
    Mostrar agora que o algoritmo está
  • 00:09:01
    correcto cóm ent H aquí a gente ya sabe
  • 00:09:05
    que me devolve a respesta respuesta
  • 00:09:08
    correcta para un vector de un atn men 1
  • 00:09:12
    considerando ISO vamos ver si lneas cuat
  • 00:09:16
    a se calculan correctamente un máximo
  • 00:09:20
    vector a de 1 n supondo que un x Está
  • 00:09:23
    correcto que un máximo de un atn men 1
  • 00:09:27
    único que estaría faltando ver
  • 00:09:30
    a última posición vector mayor menor que
  • 00:09:34
    xo exatamente que estamos
  • 00:09:38
    l cer cono demra que algoritmo realment
  • 00:09:43
    está
  • 00:09:47
    coro desp de ver algoritmo Está correcto
  • 00:09:50
    próximo paso
  • 00:09:52
    calcular que
  • 00:09:57
    cons para
  • 00:09:59
    vamos estimar cuá tempo a máquina gastar
  • 00:10:02
    o cu de memoria será necesar para
  • 00:10:04
    resolver una instancia de
  • 00:10:06
    problema forma simples deero ser
  • 00:10:09
    simplesmente colocar colocar algoritmo
  • 00:10:12
    no inicio y colocar que peg horario de
  • 00:10:17
    inicio horario de yer a diferen no prio
  • 00:10:21
    programa vamos estimar tempo de manea
  • 00:10:25
    experimental vamos suos aquí do algoros
  • 00:10:30
    ese verm y ese otro aquí de ponchos son
  • 00:10:33
    do algoritmos que resolv un mismo
  • 00:10:36
    problema aquí est mostrando tempo que
  • 00:10:39
    demora para resolver varias
  • 00:10:42
    instancias aquí
  • 00:10:47
    instancias varias instancias yo es do
  • 00:10:50
    algoritmos est mostrando aquí
  • 00:10:53
    tempo que
  • 00:10:57
    cons vemos Que o
  • 00:11:00
    vermelin consue resolver todos problemas
  • 00:11:04
    todas instancias desp todas instancias
  • 00:11:07
    ese problema enant de punos ve no consue
  • 00:11:12
    resolver problema noo máximo determinado
  • 00:11:15
    aquí significa que no terminó did not
  • 00:11:18
    Finish DEA forma veces comparamos
  • 00:11:22
    algoritmos de manea
  • 00:11:24
    experimental a gentea de saber
  • 00:11:27
    cuor que real cons enmos de entrada es
  • 00:11:31
    de aquí de manea
  • 00:11:33
    experimental
  • 00:11:36
    simples
  • 00:11:39
    veamos novamente pas de para problema de
  • 00:11:44
    ordena queremos ordenar un vector a de
  • 00:11:47
    una n de manea crescente y no entrada
  • 00:11:52
    esencia de números 23 21 28 etc y a
  • 00:11:57
    saída acia
  • 00:11:59
    ordenada certo vamos ver primero agora o
  • 00:12:03
    algoritmo de ordenación por inser o que
  • 00:12:06
    que y para eso vamos Mostrar como que
  • 00:12:10
    funciona con una instancia en particular
  • 00:12:14
    eh posición J en algú momento algoritmo
  • 00:12:18
    de ordenación por inser que que posición
  • 00:12:22
    J men Un vectores ordenado si vedes
  • 00:12:26
    observan
  • 00:12:27
    aquí toda esa parte en amarelo está
  • 00:12:31
    ordenada está y vamos tentar inserir
  • 00:12:35
    toda esa parte aquí no está ordenada
  • 00:12:37
    Vamos tentar inserir o valor que está
  • 00:12:39
    posición J no lugar
  • 00:12:42
    certo eso de aquí ese elemento que
  • 00:12:45
    deseamos inserir no lugar certo ISO o
  • 00:12:48
    que o algoritmo que tenter o algoritmo
  • 00:12:51
    de ordena por inser por eso que se Chama
  • 00:12:54
    de inser porque tenta inserir un
  • 00:12:57
    elemento no lugar certo
  • 00:13:00
    c vamos guardar esa
  • 00:13:03
    posición eh ese valor
  • 00:13:07
    verd Chave esa vari Chave est guardando
  • 00:13:12
    es2 que
  • 00:13:15
    desira parte
  • 00:13:17
    vor y
  • 00:13:19
    guardamos vari
  • 00:13:21
    Chave Okay aquí estamos
  • 00:13:25
    como un problema que queremos resolver
  • 00:13:29
    que que
  • 00:13:30
    vamos
  • 00:13:32
    que2 queer colar lugar certo Okay o que
  • 00:13:37
    queos vamos ir comparando con todos
  • 00:13:39
    elementos y empurrando elementos que son
  • 00:13:43
    mayores a vamos
  • 00:13:46
    perguntar aave mayor
  • 00:13:49
    que no emp elemento yamos vamos comparar
  • 00:13:57
    con7 a
  • 00:13:59
    que2 mayor
  • 00:14:01
    que7 no
  • 00:14:05
    emp con3 aave mayor que 23 no
  • 00:14:12
    amos con 21 aave que
  • 00:14:16
    22 mayor que 21
  • 00:14:19
    samos empar elementos y
  • 00:14:24
    colamos lug
  • 00:14:26
    y cer
  • 00:14:29
    O 22 lugar certo y que queora
  • 00:14:33
    noo parte vector ordenado yotra parte
  • 00:14:38
    vector que no está ordenado certo yora
  • 00:14:42
    mmo proco para próximo elemento que serí
  • 00:14:47
    25 colocamos ji
  • 00:14:51
    jalando a
  • 00:14:53
    posición posición está elemento 2
  • 00:14:56
    guardamos 25 variável Chave y vamos
  • 00:15:00
    tentar o mesmo yos mesmas perguntas a
  • 00:15:04
    Chave mayor que 28 no empur aave mayor
  • 00:15:08
    27 no emp aave mayor que
  • 00:15:14
    23 ent
  • 00:15:19
    25i certo se aquí cu que proco que a
  • 00:15:24
    gente a gente está comparando 25 con
  • 00:15:27
    todos elementos que est antes del y
  • 00:15:29
    empurrando elementos que son mayores no
  • 00:15:32
    pior dos casos a gente que empurrar
  • 00:15:35
    todos es elementos que est aquí certo y
  • 00:15:39
    ahí continuamos agora
  • 00:15:42
    queos parte vector ordenado continuamos
  • 00:15:45
    con próximo elemento que ser colocar o
  • 00:15:47
    24 no lugar certo y agora vamos o mesmo
  • 00:15:51
    con 24 empur 2 empur 2 empur 25 pergamos
  • 00:15:57
    si aave mayor que 23 no os 24 lugar
  • 00:16:02
    certo de noos agora parte que está
  • 00:16:06
    ordenada está faltando 29 o 29 ahos o
  • 00:16:12
    mesmo pergamos con cada un elementos not
  • 00:16:14
    que seos n elementos a gente prisar no
  • 00:16:19
    pior casos vamos que aquí temos elemento
  • 00:16:23
    no lugar de
  • 00:16:25
    2os noor casos a gente que empurrar n -
  • 00:16:29
    1 elementos certo es importante notar
  • 00:16:32
    depois para anális algoritmo n caso a
  • 00:16:35
    gente no preciser nada porque femos
  • 00:16:38
    apenas pergunta o 29 mayor que 28 s ent
  • 00:16:43
    coloca posición y+ pronto y acabó
  • 00:16:47
    finalmente vetor
  • 00:16:50
    ordenado completamente desde posición
  • 00:16:54
    posición n Aquí está
  • 00:16:56
    pudo algoritmo ordena por ehos aquí ent
  • 00:17:02
    rece como parmetro vector y n que sero
  • 00:17:06
    vector estamos trando con vectores desde
  • 00:17:10
    n importante notaro parición do
  • 00:17:15
    atn que ir guardando Chave elemento que
  • 00:17:19
    desar lugar
  • 00:17:22
    certo esa parte de aquí
  • 00:17:25
    cu se queer
  • 00:17:29
    perguntar aave mayor que elemento
  • 00:17:33
    posición
  • 00:17:34
    y seave mayor empurrando elementos es de
  • 00:17:40
    aquí Ur
  • 00:17:42
    elementos que simula con es inst y final
  • 00:17:47
    cuandoo no se verd aoca aave posición
  • 00:17:53
    yto es aquí algoritmo de ordena por
  • 00:17:57
    inser
  • 00:18:02
    test ese algoritmo no verdad se joda ese
  • 00:18:06
    algoritmo o
  • 00:18:08
    pensa Cuántas veces son feitas voy botar
  • 00:18:11
    un poquillo aquí Cuántas Cuántas compara
  • 00:18:15
    es
  • 00:18:15
    algoritmo que
  • 00:18:18
    compara compara aquí aquí y aquí si por
  • 00:18:23
    exemplo garía de contar Cuántas compares
  • 00:18:26
    algoritmo a podería ese gráfico aquí
  • 00:18:31
    eh aquí para un vector deño n de uno n
  • 00:18:35
    fixo un suor deo eh 60 cuas compara
  • 00:18:42
    realiza algoritmo anterior a gente poder
  • 00:18:46
    rodar con instancias diferentes claro de
  • 00:18:48
    mesmo 60 un número de compara a conta de
  • 00:18:53
    algo número de compara a encontrar por
  • 00:18:57
    exemplo de aquí que aquí a gente no para
  • 00:19:01
    un problema deo 40 por exemplo 60 para
  • 00:19:08
    unmo un número de compar
  • 00:19:11
    diferente aquí gente
  • 00:19:16
    aquí pior
  • 00:19:20
    caso y también un mellor
  • 00:19:24
    caso que sería es de
  • 00:19:27
    aquí
  • 00:19:32
    cierto y también teng un caso medio
  • 00:19:44
    medo mesmo para una
  • 00:19:46
    instancia
  • 00:19:48
    mesmo comportamentos verdad un número de
  • 00:19:52
    comparaciones diferentes a gente podería
  • 00:19:55
    medir otras cosas por exemplo no somente
  • 00:19:57
    un número de
  • 00:19:58
    podería ser un número de atribui en
  • 00:20:02
    número de linas que son executadas os
  • 00:20:06
    varias formas de medir cu que consumo
  • 00:20:10
    deo
  • 00:20:12
    algoritmo vamos que queremos contar un
  • 00:20:15
    número máximo de
  • 00:20:17
    atribu número máximo de atribu que
  • 00:20:21
    atribu
  • 00:20:23
    aquí
  • 00:20:25
    aquí aquí aquí
  • 00:20:29
    noer
  • 00:20:30
    atribu aquí atribu aquí tamb y aquí
  • 00:20:35
    tambén vamos contar cuas que número máx
  • 00:20:40
    de algoritmo
  • 00:20:43
    eh es de
  • 00:20:45
    aquí es prima
  • 00:20:50
    lerri verd por que n n para contaras
  • 00:20:55
    atrion aquí men
  • 00:20:59
    do má ser número de atri
  • 00:21:03
    que
  • 00:21:06
    certo que cont que má para
  • 00:21:10
    pod aquí má que igual a n a gente está
  • 00:21:15
    contando atribu por atribui que trab
  • 00:21:19
    cuantas atribu
  • 00:21:22
    doer menos que l un a do a TR men
  • 00:21:29
    atribu cuas atribu
  • 00:21:33
    cuero yora es par de aquí importante
  • 00:21:37
    Cuántas ve empurra aquí Cuántas atribu
  • 00:21:40
    son feitas aquí que enas palas sertas ve
  • 00:21:45
    que empurra elemento no pior casos a a
  • 00:21:49
    máxima cuantidad quee empurrar ser que
  • 00:21:54
    vi exemp que para último elemento pior
  • 00:21:58
    casos podería empurrar n-1
  • 00:22:01
    elementos certo ahí pueder n-2 etc etc y
  • 00:22:06
    para posiciones iniciales vaer do y 1 no
  • 00:22:12
    máximo eso de aquí dar
  • 00:22:16
    que
  • 00:22:17
    eh n por n 1 sobre 2 es somatoria eh da
  • 00:22:23
    es resultado o mesmo acontecer cona se y
  • 00:22:28
    depois a L s ser o mesmo que a L do 3
  • 00:22:31
    que n - 1 se a gente a somat deo ISO o
  • 00:22:35
    resultado ser n 3n -
  • 00:22:40
    3 número máximo de atribu menor ig n 3n
  • 00:22:46
    - 3 not que a gente un cálculo a atribu
  • 00:22:51
    que for
  • 00:22:54
    realizad pens en Consumo de de consumo
  • 00:22:58
    de tempo por cada l de ex a gente contar
  • 00:23:02
    Cuántas ve executada cada l considerando
  • 00:23:06
    que cada l cons unid
  • 00:23:10
    deo vamos contaro esa l de aquí ser ex n
  • 00:23:15
    ve de aquí ser n ve n n a sa que n tamb
  • 00:23:23
    y
  • 00:23:25
    a ser
  • 00:23:28
    desp vamos pasor a c y a que vies
  • 00:23:32
    n n etc
  • 00:23:36
    etc certo
  • 00:23:38
    [Música]
  • 00:23:39
    aer ve a porque que verificar má ve para
  • 00:23:45
    poro que aquí
  • 00:23:47
    má
  • 00:23:49
    considerando c aquí ser do
  • 00:23:56
    finala deoo
  • 00:23:58
    dar ese total de aquí 3n mán -8 porora
  • 00:24:04
    estamos calculando cu que cons
  • 00:24:08
    considerando que cada l cons unid
  • 00:24:12
    deo
  • 00:24:14
    eh tambén podemos considerar ser má
  • 00:24:18
    detal aí y considerar que cadaa y de có
  • 00:24:22
    consum unidades de tiempo Cada deas
  • 00:24:25
    consum unidades de tiempo diferente
  • 00:24:29
    ISO aar n expr no Mostrar como que feo
  • 00:24:33
    es
  • 00:24:34
    cálculo multiplicar
  • 00:24:37
    cada cada un valores que tamos slide
  • 00:24:40
    anterior
  • 00:24:41
    por no final vamos expr tipo ser expr C2
  • 00:24:46
    n c1 c en que C2 c y
  • 00:24:51
    C constantes Que depend
  • 00:24:54
    ti verdad a gente varos cálculos
  • 00:24:58
    diferentes formas de calcular o consumo
  • 00:25:00
    de tempo de algoritmo cuando calculamos
  • 00:25:02
    número de atribui chegamos n ese result
  • 00:25:06
    cuando consideramos que amos computar
  • 00:25:09
    todas linas que foron executadas no
  • 00:25:11
    algoritmo considerando que cada una
  • 00:25:14
    consume una unidad de tempo lamos n ese
  • 00:25:16
    resultado y cuando consideramos que cada
  • 00:25:18
    una consume ti unidades de tempo lamos n
  • 00:25:21
    otro resultado má será que para un n
  • 00:25:25
    Grand diferencia Fer una contag t
  • 00:25:29
    deter esa de aquí muo má
  • 00:25:32
    detal será que diferen a gente Vero de
  • 00:25:37
    aquí a ent n noas análises vamos ficar
  • 00:25:41
    satisfeitos anális má aproximadas
  • 00:25:44
    pretendemos medir apenas a ordem de
  • 00:25:46
    grandeza función de tempo algoritmo cu
  • 00:25:49
    consum algoritmo Queremos saber para n
  • 00:25:53
    grandes parao vamos introducir alguns
  • 00:25:56
    conitos que
  • 00:25:59
    son n ese caso anotación o teta y ega o
  • 00:26:05
    oma y teta es conitos será apresentados
  • 00:26:09
    Noa próxima
  • 00:26:11
    aula ent espero quean gostado de esa
  • 00:26:14
    aula y no percan a nua aula número
  • 00:26:19
    [Música]
  • 00:26:26
    do
  • 00:26:27
    [Música]
  • 00:26:39
    [Música]
  • 00:26:49
    [Música]
  • 00:26:56
    ah
  • 00:26:59
    [Música]
  • 00:27:05
    Oh
Tags
  • algoritmos
  • análise de algoritmos
  • correção de algoritmos
  • tempo de execução
  • complexidade
  • ordenação
  • problemas computacionais
  • instâncias
  • métricas
  • engenharia da computação