Projeto e Análise de Algoritmos - Aula 10 - Ordenação em tempo linear

Summary

This video script delves into the realm of linear time complexity sorting algorithms. It introduces and explains three specific algorithms: Counting Sort, Radix Sort, and Bucket Sort. The script discusses the prerequisites for each algorithm, such as the range of input values and the nature of the data. It provides step-by-step explanations of how each algorithm functions, including the use of auxiliary arrays and accumulation techniques. The video also touches on the stability of sorting algorithms and the time complexity considerations for each method, offering insights into their practical applications and efficiency.

Takeaways

• 📚 The lecture introduces linear time complexity algorithms, focusing on Counting Sort, Radix Sort, and Bucket Sort.
• 🔢 Counting Sort is based on the assumption that the input elements are integers within a known range, allowing for a direct placement of elements in the sorted array.
• 📈 Radix Sort is highlighted for sorting numbers based on their individual digits, starting from the least significant digit to the most significant.
• 📝 Bucket Sort is explained as a method suitable for uniformly distributed data within a specific range, dividing the data into 'buckets' and then sorting each bucket individually.
• 💡 Counting Sort uses a counting array to determine the position of each element, ensuring that elements with the same value maintain their original order, making it a stable sorting algorithm.
• 📊 Radix Sort involves multiple passes, sorting by each digit in sequence, and requires a stable sorting algorithm for each pass to maintain the original order of equal elements.
• 🗂️ Bucket Sort divides the range [0, 1] into 'n' buckets and uses insertion sort to order elements within each bucket, which is efficient when the distribution of elements is uniform.
• 🕒 The time complexity of Counting Sort is O(n+k), where 'n' is the number of elements and 'k' is the range of input values.
• 🔄 The time complexity for Radix Sort depends on the number of digits 'd' and the time complexity of the stable sorting algorithm used in each pass, typically O(d*n).
• 🌐 The efficiency of Bucket Sort is contingent upon the uniformity of data distribution; if the data is uniformly distributed, the expected time complexity is linear, O(n+k).
• 🔑 The script emphasizes the importance of understanding the nature of the data (e.g., range, distribution) when selecting an appropriate sorting algorithm for optimal performance.

Q & A

What is the main topic of the video script?

The main topic of the video script is linear time complexity sorting algorithms, specifically counting sort, radix sort, and bucket sort.

What is the time complexity of comparison-based sorting algorithms?

The time complexity of comparison-based sorting algorithms is Ω(n log n), where n is the number of elements to be sorted.

What is counting sort and how does it work?

Counting sort is a non-comparison-based sorting algorithm that works by counting the number of objects that have a distinct key value and using arithmetic to determine the positions of each key in the output sequence.

What is the precondition for using counting sort?

The precondition for using counting sort is that the input consists of integers in a small range, and you know the range of possible values beforehand.

How does radix sort differ from counting sort?

Radix sort differs from counting sort in that it processes the input numbers digit by digit, starting from the least significant digit to the most significant, using a stable sort for each digit.

What is bucket sort and how does it operate?

Bucket sort operates by distributing elements into several 'buckets' and then sorting these buckets individually, often using insertion sort, before concatenating the buckets to get the final sorted list.

What is the significance of the term 'stable' in sorting algorithms?

A 'stable' sorting algorithm is one that maintains the relative order of records with equal keys (i.e., values) as they appeared in the input.

What is the time complexity of bucket sort if the elements are uniformly distributed?

If the elements are uniformly distributed, the expected time complexity of bucket sort is O(n + k), where n is the number of elements and k is the number of buckets.

How does the script mention the use of an auxiliary array in counting sort?

The script mentions the use of an auxiliary array to count the occurrences of each element and to determine the position where each element should be placed in the final sorted array.

What is the importance of maintaining the original order in stable sorting algorithms?

Maintaining the original order in stable sorting algorithms is important when the same elements appear multiple times in the input, ensuring that their relative order is preserved in the sorted output.

What is the script's stance on the efficiency of sorting algorithms?

The script suggests that the efficiency of sorting algorithms can be determined by their time complexity, with linear time complexity algorithms being particularly advantageous for large datasets.

Outlines

00:00

📚 Introduction to Linear Sorting Algorithms

This paragraph introduces the topic of linear sorting algorithms, focusing on those that operate in linear time complexity. It mentions several linear sorting algorithms, including counting sort, radix sort, and bucket sort, and highlights their unique characteristics. The speaker explains that these algorithms utilize operations other than comparison to determine the sorted sequence, which is a departure from traditional comparison-based sorting algorithms. The paragraph also sets the stage for a detailed explanation of each algorithm in subsequent sections.

05:02

🔢 Detailed Explanation of Counting Sort

The second paragraph delves into the specifics of counting sort, an algorithm that assumes the input consists of integers within a small range. The process involves counting the occurrences of each element and using this information to determine the sorted order. The speaker provides a step-by-step walkthrough of how counting sort works, including the use of auxiliary arrays to count occurrences and to place elements in their correct positions. The paragraph also discusses the time complexity of counting sort, emphasizing its linear performance with respect to the number of elements being sorted.

10:04

🔡 Radix Sort and its Iterative Digit-by-Digit Approach

This paragraph discusses radix sort, an algorithm that sorts numbers based on their individual digits. The explanation begins with the assumption that the numbers have a fixed length, such as a certain number of digits. The process involves sorting the numbers by each digit, starting from the least significant to the most significant, while maintaining the previous order from the previous digit's sort. The speaker illustrates how radix sort can be implemented using a stable sorting algorithm for each digit, and the importance of using a stable sort to preserve the original order of equal elements.

15:05

📊 Bucket Sort and Its Uniform Random Distribution Assumption

The fourth paragraph introduces bucket sort, which is based on the assumption that the input elements are uniformly distributed within a specific range. The algorithm divides the range into several 'buckets' and distributes the elements among these buckets. It then sorts the elements within each bucket using insertion sort and finally concatenates the sorted elements from all buckets to produce the final sorted list. The speaker explains the process with an example and discusses the expected time complexity, which depends on the uniform distribution of elements among the buckets.

20:08

🎓 Conclusion of Linear Sorting Algorithms Lecture

The final paragraph wraps up the lecture on linear sorting algorithms. It summarizes the key points covered in the lecture and expresses hope that the audience found the content engaging and informative. The paragraph ends with a musical note, signifying the conclusion of the session.

Keywords

💡Linear Time Algorithm

A linear time algorithm is one that has a time complexity of O(n), where 'n' is the size of the input. It means the time it takes to process the input scales linearly with the input size. In the context of the video, linear time algorithms are discussed in relation to sorting algorithms that can potentially sort data in a time proportional to the number of elements being sorted, which is a highly desirable property for efficiency.

💡Counting Sort

Counting sort is a linear time sorting algorithm used when the range of input data is known and not significantly larger than the number of objects to be sorted. It operates by counting the number of objects that have each distinct key value and using arithmetic to determine the positions of each key. In the video, counting sort is mentioned as the method used to sort elements in linear time, given the preconditions are met.

💡Bucket Sort

Bucket sort, also known as bin sort, is a distribution sort that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or by recursively applying the bucket sorting algorithm. The video script discusses bucket sort as an algorithm that divides the range [0, 1] into 'n' buckets and sorts the numbers within each bucket using insertion sort.

💡Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it provides a good example of a stable sort, and in the video, it is used as a secondary sorting method within each bucket in the bucket sort algorithm.

💡Stable Sort

A stable sort is an algorithm that maintains the relative order of records with equal keys (values). In the context of the video, stability is important when sorting numbers by their digits because it ensures that the original order of equal elements is preserved. The script mentions that bucket sort and counting sort are stable sorts, which is crucial for maintaining the order of elements with the same value.

💡Digit by Digit Sorting

Digit by digit sorting is a technique used in sorting algorithms to sort numbers based on each digit, starting from the least significant digit to the most significant. This method is used in radix sort, and the video script refers to a similar approach where numbers are sorted by their individual digits, ensuring that the order of numbers with the same leading digits is maintained.

💡Comparison-Based Sorting

Comparison-based sorting algorithms determine the order of elements by comparing them to one another. The video script mentions that any comparison-based sorting algorithm must perform at least Omega(n log n) comparisons in the average and worst cases, highlighting the lower bound for comparison sorts.

💡O(n) Notation

O(n) notation, also known as linear notation, describes an algorithm's performance in terms of the number of basic operations it performs in relation to the input size 'n'. In the video, O(n) is used to describe the time complexity of certain sorting algorithms that can operate in linear time, which is an optimal performance for sorting large datasets.

💡Asymptotic Behavior

Asymptotic behavior refers to the behavior of a function as its argument approaches infinity or negative infinity. In the context of the video, the term is used to describe the performance of sorting algorithms, specifically how their efficiency scales with the size of the input data. Algorithms that are asymptotically optimal, such as those with O(n log n) complexity, are desirable for large datasets.

💡Radix Sort

Radix sort is an integer sorting algorithm that sorts data with integer keys by grouping the keys by the individual digits which share the same significant position and value. The video script discusses a variant of radix sort, known as 'adic short', which sorts numbers based on their digits, starting from the least significant to the most significant.

💡Bucketing

Bucketing is the process of distributing elements into different buckets or groups based on certain criteria. In the context of bucket sort, the video script describes bucketing as the initial step where numbers are distributed into buckets based on their value ranges, which is a critical step before applying insertion sort to each bucket.

Highlights

Introduction to linear time algorithms.

Discussion on comparison-based sorting algorithms and their lower bound of Omega(n log n) comparisons.

Introduction to Counting Sort, a linear time algorithm used for sorting integers within a certain range.

Explanation of how Counting Sort works when elements are known to be within a specific interval.

Use of an auxiliary array in Counting Sort to count the occurrences of each element.

The process of placing elements in their correct position using the count array in Counting Sort.

Maintenance of the original order in Counting Sort for elements with the same value.

Analysis of the time complexity of Counting Sort, which is linear, O(n).

Introduction to Radix Sort, another linear time algorithm suitable for sorting numbers with known digits.

Description of how Radix Sort works by sorting numbers digit by digit, starting from the least significant digit.

The importance of using a stable sorting algorithm for the intermediate steps in Radix Sort.

The process of sorting numbers by the most significant digit after sorting by the least significant in Radix Sort.

Analysis of the time complexity of Radix Sort, which depends on the number of digits and the intermediate sorting algorithm used.

Introduction to Bucket Sort, suitable for sorting randomly distributed numbers within a uniform range.

Explanation of how Bucket Sort divides the range into buckets and distributes elements accordingly.

The use of Insertion Sort on each bucket in Bucket Sort to sort individual elements within the buckets.

Analysis of the expected time complexity of Bucket Sort, which is linear if the distribution is uniform.

Conclusion of the lecture with a summary of the discussed linear time sorting algorithms.

Transcripts

[Música]

i

[Música]

hola pesos sean vendidos a nosa aula

número de 'aces' de proyecto y análisis

de algoritmos esta ola es sobre

ordenanza o en tiempo lineal

primero vamos a tener una introducción

vamos a hablar un poco sobre varios

algoritmos que son lineales entre las

ordenación por contagio adic short y

baquet soft

vimos las aulas anteriores varios

algoritmos de ordenación cualquier

algoritmo basado en comparaciones debe

efectuar omega de en el lobby de n

comparaciones núcleo el caso y ya vimos

que eso implica en que omer shatz sort

son asintóticamente o chinos

de mesa o la vamos a presentar algunos

algoritmos que son lineales entre el iso

algoritmo de ordenación por contagien ya

dixon y baguette son estos algoritmos

utilizan otras operaciones diferentes de

operación de comparación para determinar

la secuencia ordenada la verdad y

ellison goya de algunas características

los dados de entrada luego un límite

inferior que omega de en el lobby de n

no se aplica para el is

pensamos un nuestro primero algoritmo

lineal o algoritmo ordenación por

contagio supone que sabemos que usa

elementos que desechamos ordenadas son

enteros un intervalo de cero acá

en ese caso si sabemos sus valores los

elementos de un osote store aunque que

podemos hacer aunque podemos hacer es

determinar para cada elemento si su

vector un número de elementos menores

que él y esa información podría ser

usada depois para y cero elementos y

directamente en un lugar ser tanto por

ejemplo supone que posee

sabe que elementos son menores

que sis en todo haití ya sabe dónde

colocar o si somos colocar en la

posición 21

el tronco que ha entrado algoritmo

ordenación por contagio

el ítem como entrada un vector a esa

posición una posición n iv ac y de un

vector b la posición u otra posición n

con los elementos de a en orden

creciente 60 empezamos aquí un ejemplo

directora s de aquí un osote héctor a

el ítem los elementos 4 3 4 3 10 36

aunque aquí sabemos que los elementos

están entre 0 y 4 seres humanos o cada 4

en este caso y vemos que existen varios

elementos repetidos por ejemplo 4 parece

aquí aparece aquí ustedes aparece aquí

aparece aquí y aparece aquí esto coloca

sus números en diferente color apenas

para indicar que la primera vez que

aparece 3 está en blanco la segunda en

amarelo la tercera en verme yo mismo

pero 4 por ejemplo

ese algoritmo de ordenación por contagio

el uso un vector auxiliar se para contar

cuántos números tengo de cada uno

y para determinar la posición en que o

elemento debe ser colocado tanto vamos a

hacer un otro vector se ese vector se va

a ser de tamaño

5 la verdad es en ese caso porque va

desde cero ática

se atentó al ivai ter tamaño camisón

porque aquí está nuestro algoritmo de

ordenación por contagio

el rcd es un vector a cantidad y

elementos su gestor que n unca que sería

l mensual desde un valor cero ante un

valor acá y v que va a ser un vector con

hielo y va a colocar sus elementos

ordenados

aquí tenemos unos ejemplo no sólo esto

que queremos ordenar lo primero que

vamos a hacer

pegar un huso vector entonces de equihua

no sólo esto se inicializar una línea

unidos y somos inicializar ese vector

con ceros porque es el vector va a

servir para contar cuántas veces aparece

4 cuántas veces apareció tres cuántas

desaparece uno y así porque al ser la

línea 3 a la línea 4 five hacer

exactamente eso para contar cuántas

veces aparece cada elemento en todo ese

vector se va a ser usado en esas esas

líneas aquí para servir como un contador

por ejemplo aquí vamos a ir a apareció 4

ok

tengo un 4

después avanzamos para siguiente

posición de moscú trace tengo tengo un 3

book contando cuántas veces aparece

vamos para posición 3

tengo un valor 4 y tengo dos elementos 4

fue para sinchi posición tengo más un

300 ahora tengo dos elementos 3

tengo un elemento próximo ok tenga un

elemento

el próximo año más un elemento con valor

3 en todas ahora tengo tres elementos 3

en tomate aquí hacia la línea 4 sabemos

que se ve y contiene un número de

elementos de entrada y huawei

después lo que vamos a hacer vamos a

acumular sus números en cee y de esa

forma en cd y vamos tener un número de

elementos de entrada que son menores o

iguales que está tomamos a acumular ese

vector sea aquí eso va a hacer falta una

línea 5 y 6 exactamente estamos

acumulando los valores aquí botero la

posición 1 tengo un elemento menor a 0

tengo dos elementos menores iguales a 1

después tenemos dos elementos menores

iguales a 2

cinco elementos menores iguales a tres y

seis elementos menores iguales a cuatro

simplemente estamos haciendo acumular

los valores aquí una vez se hizo ahora

ya sabemos oye colocar cada uno de los

elementos no vectores aída que un vector

b

comenzamos de final si sabes qué

comenzamos aquí 23 sabemos

ahora sabemos dónde colocar ese elemento

3 como que sabemos si se halla y sabe

que existen 5 elementos menores iguales

a trace se al tanto debo colocar ese 3

la posición 5

que no posee un 5 ok

y después ahora tenemos vamos a

disminuir la cantidad de elementos

menores o iguales a 3 a core 4

y continuamos ahora vamos por la

posición original vector 6

vamos aquí la posición 6 aparece un 0

hoy equivoco lo conocerá una posición

vamos para 5 ago 25

la posición 5 o el elemento 18 que fue

colocar o elemento 1 o joaquino vector

se debe estar la posición 2 o colocar

aquí en la posición 2 y continuamos

ahora un

[Música]

trace oye que hubo colocar un elemento

38 aquí en esa posición en cuatro

elementos menores iguales a tres el

tiempo coloca una posición 4

el hombre en que esos valores en cáncer

disminuyó sabores se va a mudar para 3

y ahí continuamos coleando en un sector

inicial vamos aquí nos vemos su 411 cómo

colocar ese 4 óleo aquí el líder está en

la posición fecha ok

aquí

oye que vamos a colocar ahora o elemento

un elemento que está en la posición 23

vamos aquí o trace el líder está en la

posición 3 de aquí

y finalmente 11 que vamos a colocar

4 vayamos aquí 4 se realizan a posición

6 colocamos el y la posición 6 bryant

que no final tenemos unos o vector

ordenado

una cosa importante de ver también qué

la orden original fue mantenida primero

estado 3

de color blanco 3 de color amarillo y

después 13 korver medio blanco amarillo

medio

o algoritmo estado porque los números

con un mismo valor aparece en el vector

de salida en la misma orden en que

aparece en el vector de entrada una

desventaja de ese algoritmo de kelly

precisa de un otro vector no si no se

soldaron entrada a marcel impreciso de

un vector de un vector de para mostrar a

seguir en todo el noa emplace

ahora analicemos cualquier consumo de

tiempo de algoritmo línea uy línea 2 en

fort que va desde cero ateca en todo el

jet eta de acá la línea 3 y 4 byte de

una tiene en tonelli

de adn a línea 5 y 6 va de una teca

entonces de tádic a la línea 68 y no vi

el ifai desde en atv entonces

fácil la suma de todos él es verdad que

está de más ser

cuando usamos su algoritmo de ordenación

por por contagio cuando cae igual

adn en este caso consumo de tiempo de

ordenación por contagio va a ser de adn

que en todo aquí sí forcall igual ordene

acción sustituir por n va a darte tarde

pasemos para un uso segundo algoritmo de

ordenación línea exterior adic short

ahora tenemos una u otra característica

sabemos una otra característica no sus

elementos supone que sabemos que usa

elementos que decíamos ordenar ten de

dígitos

si sabemos que tendré dígitos ahora y va

a ser ordenar en función de seis dígitos

usar esa información

como que vais a efecto hizo vamos a

ordenar en función dos dígitos

considerando uno de cada vez cosas

comenzando pelo dígito menos

significativo

de ese modo

si vamos comenzar un dígito menos

significativas en kuwait el que pase va

a ser apenas de pasajes de la lista de

elementos para poder ordenar esa lista

dada entonces ya hemos aquí un ejemplo

supone que bo set en un siguiente

elementos todos esos de aquí 491 348 736

etcétera etcétera cuantos dígitos estén

todos esos números el existen tres

dígitos en cómo llamar a cantidad

dígitos de chihuahua 3 cuántos números

del peñón esa lista

enseñó oit o números en eua white aunque

que vais fasero algoritmo haddix short

el barrio ya los dígitos comenzando pelo

dígito menos significativo en trabajamos

un dígito menos significativo de qué

vamos a hacer vamos a ordenar por ese

dígito menos significativo entonces está

primero primero va a estar s después va

a estar ese después ese

después es de aquí después sus tres

hijos que vamos a ver aquí son primero 1

2 3 5 6 y 8 ya no son para un dígito

menos significativo una vez que fue

feita es ordenación hago lo llamamos

para un segundo dígito menos

significativo que se ayude un medio ahí

vamos a hacer un mes no vamos a comenzar

a ordenar los elementos de acuerdo con

ese dígito por él vamos mantener a orden

inicial que fue fecha antes aquí sin

perder esa orden 70 vamos a ver aquí

tenemos a xente vai ter coloca primero

ese 1

y después no tenemos dos después tenemos

su trace lo que primero vamos a colocar

ese 3 de aquí porque estaba sin nada una

ordenación anterior y después vamos a

colocar ese elemento que tenga ese

dígito 3 número que desde aquí

y así por ians después eeuu 4 714 y un

resultado va a ser este de aquí

ok

y ahí continuamos ahora vamos a hacer un

mismo con un 3º dígito vamos a ordenar

pero tercero dígito y enojo mantén la

ordenación anterior talento que dígitos

tenemos aquí tenemos un 2 tanto primero

va a estar ese dígito ese es el elemento

que tengo primero dígito sería ese

primero va a estar los 111 después va a

estar

[Música]

231 de puesto que tengo dígito 3 que

sería este de aquí después que tengo un

dígito 4 tendones que están visitó 4 el

embrión que está gente que mantenga

orden original se halla primero tienen

que decir 1 491 y después o 492 eso de

ahí importante precisamos para facer esa

ordenación de un algoritmo estable tanto

para facer ordenación por distintos

préstamos de un algoritmo estado y

acabamos de ver en esa misma aula qué

algoritmo de ordenación por contagio en

un algoritmo estado entró podríamos usar

el zoom junto con un algoritmo

secundario para facer la ordenación por

handy short como resultado final va a

ser este de aquí es en que usa elementos

mágicamente fueron ordenados

aquí está un peso del código de

algoritmo haddix ortelli recibe un

vector a la cantidad ya elemento cn a

cantidad 7 dígitos de todos esos

elementos eleva a un dígito menos

significativo a tu dígito más

significativo y vaya ordenando el vector

pelo dígito y

importante fallar si no hubo que ese

algoritmo usado aquí en la ordenación

debe ser un algoritmo estado el consumo

de tiempo de ese algoritmo va a depender

del consumo de tiempo de ese algoritmo

intermediario que usado en la línea 2

si cada dígito está en intervalo de 0

acá menos 1 y acá no es muy grande

podemos usar ordenación por contagio por

ejemplo si tenemos un números que son

decimales agentes y sabes que los

dígitos van de 0 en off y no podemos

usar la ordenación por contagio en este

caso es un constante

sería days ok si fuésemos en todo

análisis y algoritmo considerando que

fue usado o algoritmo de ordenación por

contagio para usted la línea 1 by de una

tv por tanto el dt de la línea 2 el bay

usar un algoritmo de ordenación

secundario y él está dentro de la zone

entonces por estar dentro de un lazo de

lazo de línea 1 en la etiqueta de veces

consumo de tiempo lo algoritmo

secundario que en ese caso si fuese

ordenación por contagio va a ser n más

acá fue haciendo asoma para usted que

nos algoritmo teta de de veces en el más

acá

si de una constante y qaeda orden n

entra un handy short en línea

y pasemos ahora no su último algoritmo

baquet sort ahora vamos a ver una u otra

característica de nuestros elementos

supone que sabemos que los elementos que

decíamos ordenar fueron generados de

manera aleatoria de forma uniforme no

intervalo y el issste a un intervalo de

0 a 1 la idea básica de ese algoritmo el

primero dividir un intervalo que va de 0

a 1 en n baquets después distribuir un n

números entre s n baquets y después

ordenar los números en cada uno de eses

baquets usando ordenación por inserción

1 final de todo ese proceso vamos tener

todos los elementos ordenados

aquí tenemos un ejemplo verán que todos

sus números están entre 0 y 1 y tenemos

seis elementos lo primero que vamos a

hacer es crear n baquets que son days en

ese caso entrante no deis baquet cada

vázquez baytelman lista ligada

11 y vamos a estar dos elementos por

ejemplo aquí no primero vamos a estar

todos los elementos que están entre 0 y

0 vírgula 11 segundos van a estar todos

los elementos que están entre 0 vincula

10 vinculados y así por ians tanto

comenzamos a ver unos elementos y vamos

colocar el is aquí en cada uno 2 baquets

lo primero va a estar si logramos aquí 1

055 faisanes selva que está aquí

continuamos con 1 033 bcn se va que 2

042 va a estar los bucks 4 después nos

va que 25 y después su 0 39 va a estar

en ese paquete 1 073 están ese 10 11

están en 1 019 va a estar en ese paquete

0 65 desde aquí 031 aquí y 0 22 aquí ok

entonces hemos en este caso days baquets

cada un tema lista de elementos secreto

y hago lo que vamos a hacer

en cada una de esas listas aplicar

ordenación princesa aplicamos ordenación

princesa aquí está ordenado aquí son

elementos ordenado no decide aquí

precisamos ordenar que tengan elementos

ordenada etcétera etcétera si aplicamos

ordenación por interesa tenemos como

resultado esto de aquí

ok y por último lo único que precisamos

hacer es simplemente por todos

estos elementos y ya tenemos unos a

lista ordenada dejan aquí 0 círculo 11

019 y después 0 22 se lo vincula 33-31

disculpen 0 circula 33 0 39 42 55 65 73

está ordenado

análisis uva que son es un poco más

complicada porque la va a depender la

distribución de los números nos baquets

la gente vio que los números son

distribuidos de manera uniforme ser si

consideramos hizo los números son

distribuidos de manera uniforme he

esperado que un número de elementos en

cada uno de ses barques ella trata de un

pose ya que en cada paquete exista plena

su mundo es ella más constante

una constante y de la misma cantidad y

constante de elementos

luego el consumo de tiempo esperado por

ordenar cada baqueta también va a ser

detalle

y si consideramos se hizo entonces como

tenemos n baquets un consumo de té budva

que solvay ser de tves cn queda de eta

de un algoritmo lineal

con esa fui a nosa aula número de este

análisis del proyecto y análisis de

algoritmos sobre ordenación lineal

espero que ustedes tengan gusta

[Música]

2

[Música]

ah

[Música]

ah

[Música]