Samenvatting
Summary Data Structures & Algorithms
Summary of everything you need to know for the DSA exam!
[Meer zien]Voorbeeld 3 van de 18 pagina's
Voorbeeld 3 van de 18 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
Data Structures and AlgorithmsInsertion Sort:
Input: sequence of n numbers
: Output: sorted permutation of the input
•
Efficient algorithm for sorting a small
number of elements
•
Algorithm sorts the input numbers in
place: it rearranges the numbers within
the array A, with at most a constant
number of them stored outside the array
at any time.
Best case performance: execute the while loop the least as possible. The array is already sorted
so the comparison test always fails. For the best case time complexity T(n) is in Θ(n)
Worst case performance: execute the while loop as many times as possible. The array is sorted
in a reversed way, so the comparison test always succeeds. T(n) = an + bn + c so T(n) is in Θ(n )
2 2
Insertion sort can be stable: the order of equal elements is respected. If the comparison would be
>= instead of > then it is not stable anymore.
Rate of growth:
Theta notation says something about the rate of growth, so we want this to be as low as
possible. To find Θ, we want to drop the lower order terms and we want to drop constants.
② asymptotic tight bound (=) 3M€ -042) 3N # ② (M) 3 € -04 )
0 asymptotic upper bound (<=) 3M€ 0cm) Îdoes not
3N C- OCN increase
r asymptotic lower bound (>=)
Useful properties big-O
na € Ocnb ) for AEB
109dm) E (nb) for alt a. b) 0
na 0lb ) for
"
c- an a> 0 ,
b > 1
for
109A ( n ) E
109ns (n ) alt a.
b > 0
IJ
,Merge sort
How do we sort?
Stop condition: if the sequence contains less than 2 elements; otherwise:
⑥
Split the sequence into 2 parts of (almost) equal length
•
Sort the two subsequences using merge sort (recursion)
•
Merge the two sorted sublists
How do we merge?
Loop: as long as both sequences are non-empty
•
Compare the first elements of both sequences
•
Remove the smallest and move it to the end of the output sequence
Last: if one of the sequences is empty, add the other to the tail of the output sequence
: Worst-case time complexity via tree analysis:
Height is log(n) for n the length of the input array (example has height log2(8) = 3)
Number of levels is log(n) + 1 (example has 3 + 1 = 4 levels)
Number of leaves is n (example has 8 leaves
T(n) = c x n x log(n) + d x n
Time complexity of merge sort is in Θ (nlog(n))
Shape of the input is unimportant. Best case = worst case time complexity
Divide is Θ(1), conquer is recursive, combine is Θ(n), so:
Time complexity via recurrence equations:
First assume n = 2
Then: 1- ( )
base
n
case
d=
it
{
Ê
if
2T ( E
=
I
) +
so
en
i =
if
109 (n)
na
n> 1
ËË
Substitute this 1-( n) n 1- ( i )
109 (n) c. n c.
Nog (n ) + d- n
=
: = .
+ .
Hence T is in ②(
mogen) )
The worst-case time complexity is better than for insertion sort, but this algorithm is
not in-place, whereas insertion sort is in-place (drawback)
, Trees:
Set of nodes with a parent-child relation
-
There is a unique distinguished node root (top node)
: Every non-root has a unique parent
A node may have successors / children
-
A node without successors is a leaf (lowest ones)
: A node with successors is internal
The depth of a node is the length of the path to the root.
: The height of a node is the maximum length of a path to the leaf.
The height of a tree is the height of the root or the maximal depth.
: A level or layer of a tree consists of all nodes of the same depth.
\
The number of levels of a tree is the height of the tree + 1
Binary tree:
- Every node has zero, one or two successors.
- Binary tree is complete if all levels are completely filled.
Binary tree is almost complete if all levels are completely filled, except possibly the lowest one
: which is filled left-to-right.
If a binary tree is complete, it is also almost complete, and therefore also normal binary.
Consider an almost binary tree of height h:
I If the lowest level contains 1 element, then number of elements n = 2^h
If the lowest level is full, then the number of elements is n = 2^(h+1) - 1
I So h = Ilog(n)I . So round down
I
X . P
if xp = nil ,
it is root
Divide and conquer paradigm: - quick sort
Divide: divide the problem into smaller sub problems - merge sort
: Conquer: solve the sub problems using recursion
-
Combine: combine the solutions to the sub problems to a solution of the original problem
Max-heap:
Max-heap is a data structure used for sorting: if we walk down the tree, the keys decrease.
: Condition on the shape: an almost complete tree.
-
Every node is labeled with a key.
s
Max-heap property on the keys: on every path from the root to a leaf, the keys are non-increasing,
that means H[parent(i)] >= H[i].
'
Hence, the max key is the root.
116 \ [ 16.14.10 11.7.9]
14 10
,
.
A min-heap would have keys that increase walking downwards. I I I
11 7
9
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 femkestokkink. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 52510 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen