in Computer Science, an algorithm is a list set of instructions, used to solve problems or perform tasks, based on the understanding of available alternatives.
It is normal to use Asymptotic Notation to explain runtime
Runtimes
Divide and Conquer Sorting Algorithms
A comparison sorting algorithm will never have a lower worst case runtime than . Bogo-sort however has average time runtime of Best case can however be much better
Quicksort Randomized Quicksort Merge-Sort
Sorting in Linear Time
If we assume that we know more about input than just comparisons, and that we don’t need to do as much with output, we can get a lower runtime.
Sorteringsgrensa Counting Sort Bucket Sort Randomized Select Radix-Sort
Binary Search Trees
Inorder Tree Walk Tree-Search Tree-Insert
Heaps
Left Parent Max-Heapify Build-Max-Heap Heapsort
Prioriteringskøer
Heap-Max Heap-Extract-Max Heap-Increase-Key Max-Heap-Insert
Runtime
Dump
Reduksjoner: Vi reduserer vanskelig problemer, ikke til vanskelige problemer. Hvis vi skal åpne en kiste: * Dersom en lås er enkel å åpne er kista lett å åpne * Dersom låsen er vanskelig å åpne er nødendigvis ikke kista vanskelig å åpne * Hvis kista er vanskelig å åpne låsen er vanskelig å åpne POENG: Vi reduserer til flere problemer, og den letteste løsningen er løsningen