Samenvatting
Summary of Data Structures and Algorithms
Summary containing information on the slides, notes, and book.
[Meer zien]Voorbeeld 4 van de 74 pagina's
Voorbeeld 4 van de 74 pagina's
In winkelwagengesponsord bericht van onze partner
Verkoper
Volgen
Voorbeeld van de inhoud
Data Structures and Algorithms0. Introduction
Asymptotic notation (Big-O)
Worst-case asymptotic running time (“upper bound”)
It provides the upper limit on how the running time of an algorithm grows as the input size
increases
Suppress:
- Constant factors – too system-dependent
- Lower-order items – irrelevant for large inputs
T(n) = O(f(n)) if and only if there exists
positive constants c and n0 such that
T(n) <= c * f(n)
for all n > n0
Classes of algorithmic complexity
Growth rate Name Code example Description
1 Constant A=b+1 Statement (one line
of code)
log(n) Logarithmic While(n>1){n=n/2} Divide in half
(binary search)
n Linear For(c=0; c<n; c++) Loop
{1+=1}
n*log(n) Linearithmic Mergesort, E ective sorting
Quicksort algorithms
n^2 Quadratic For(){For(){}} Double loop
n^3 Cubic For(){For(){For(){}}} Triple loop
2^n Exponential Trying to break a Exhaustive search
password by
generating all
possible
combinations
Asymptotic notation (Big Ω)
Best-case asymptotic running time (“lower bound”)
ff
, It provides a lower limit on how quickly the running time can grow as the input size
increases.
If Big-O <= then Big Ω >=
T(n) = Ω(f(n)) if and only if there exists
positive constants c and n0 such that
T(n) >= c * f(n)
for all n >= n0
Asymptotic notation (Big θ)
“Precise bound”
It indicates that the running time grows at the same rate as a speci c function for
su ciently large input sizes.
If Big-O <= and Big Ω >=
then Big θ =
T(n) = θ(f(n)) if and only if there exists
positive constants c1, c2 and n0 such that
c1 * f(n) <= T(n) <= c2 * f(n)
for all n >= n0
Primary school algorithm
Karatsuba multiplication
Big-O: 3 recursive steps of n/2-digit numbers — O(n^(log2(3))) = O(n^1.59)
Input: two n-digit positive integers x and y.
Output: the product x * y
Assumption: n is a power of 2
—————
If n = 1 then
compute x * y in one step and return the result
Else
a, b := rst and second halves of x
c, d := rst and second halves of y
ffi fi fi
, compute p := a + b and q := c + d using grade school addition
recursively compute ac := a * c, bd = b * d, and pq := p * q
compute adbc := pq - ac - bd using grade school addition
compute 10^n * ax + 10^(n/2) * adbc + bd using grade school addition
return result
Recursive multiplication algorithm
Big-O: 4 recursive steps — O(log(max(a, b))
Input: two n-digit positive integers x and y.
Output: the product x * y
Assumption: n is a power of 2
—————
If n = 1 then
compute x * y in one step and return the result
Else
a, b := rst and second halves of x
c, d := rst and second halves of y
recursively compute ac := a * c, ad := a * d, bc := b * c, and bd = b * d
compute 10^n * ac + 10^(n/2) * (ad + bc) + bd using grade school addition
return result
NOTE: in karatsuba we only need to compute ac, bd and (a + b)(c + d)
Calculation complexity - recursive algorithms
Master method
T(n) <= a * T(n/b) + O(n^d)
Where
a: number of recursive calls
b: input size shrinkage factor (how fast my input shrinking with code, recursive call)
d: exponent in running time of the “combine step”
1. Sorting
The naive approach for sorting an array of integers: get the minimum, print it, remove it from the
array, and repeat.
fi
, Selection sort
Big-O: n the number of items in the list — O(n^2)
This is comparison-based sorting algorithm. It works by dividing the input list into two parts: a
sorted and unsorted portion. The algorithm repeatedly selects the smalles (or largest, depending
on the order) element from the unsorted portion and moves it to the end of the sorted portion.
This is repeated until the entire list is sorted.
Steps:
1. Start with the rst element of the list as the current minimum (of maximum)
2. Compare the current minimum with each element in the unsorted portion of the list. If a
smaller element is found, update the current minimum to that element.
3. Once iterated through the unsorted portion and the smallest element is identi ed, swap it with
the rst element in the unsorted portion. This e ectively moves it to the end of the sorted
portion.
4. Repeat the process, considering the next element (i = i +1) as the current minimum, and
comparing it with the remaining unsorted elements.
5. Continue these steps until the entire list is sorted. The sorted portion will grow, and the
unsorted portion will shrink with each iteration.
3 17 5 25 1 Sorted = ∅
Current min Unsorted = A
Compare cur_min with all other elements.
1 < 3; therefore set cur_min = A[1] and swap 3 with 1
1 17 5 25 3 Sorted = A[0]
Unsorted = A[1] -
Current min
A[4]
3 < 17; swap 17 with 3
1 3 5 25 17 Sorted = A[0] - A[1]
Unsorted = A[2] -
Current min
A[4]
1 3 5 25 17 Sorted = A[0] - A[2]
Unsorted = A[3] -
Current min
A[4]
17 < 25; swap 25 with 17
1 3 5 17 25 Sorted = A[0] - A[4]
Unsorted = ∅
Input: unsorted array A of length n
fi
fi ff fi
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper mchelleh. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €15,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 73918 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen
