Programování
Algoritmy
Co je to algoritmus?
Algoritmus je pracovní postup, který má tyto povinné vlastnosti.
- Rezultativnost.
To znamená, že vždy vydá nějaký výsledek. - Finitnost (konečnost).
To znamená, že někdy skončí. Jinými slovy, skončí po konečném počtu provedených kroků. - Elementárnost (jednoduchost) popisu.
Algoritmus je popsán konečným počtem základních instrukcí. Tedy takových, o kterých je jasné, jak se provedou (a tedy neumožňují žádný osobitý výklad některého vykonavatele). - Determinovanost (jednoznačnost).
Postup práce je jasně daný a vždy závisí pouze na popisu algoritmu a na vstupu („pracovní materiál“, ať už jde o vejce, nebo o informace, tedy nějaká čísla). Na průběh algoritmu nemá žádný vliv náhoda nebo svobodná vůle vykonavatele.
Algorimy jde vyjádřit více způsoby, avšak sami o sobě jsou jen myšlenka.
- Slovně.
jednotlivé kroky postupu jsou vyjádřeny větami v přirozeném jazyce - Graficky
jednotlivé kroky jsou popsány grafickými značkami se slovním popisem, například pomocí tzv. vývojových diagramů - Matematicky
soustavou rovnic, vztahem mezi veličinami - Programem
jednotlivé kroky jsou popsány instrukcemi určitého procesoru
Výpočet časové složitosti
Výpočet časové složitosti nám udává teoretický odhad kolik kroků musí algoritmus udělat, než vrátí výsledek. Tento je zavislý na počtu prvků, které algoritmus zpracovává. Tento počet označujeme jako n.
Kdybychom měli projet všechny prvky v poli, které má n prvků, tak nám to zabere O(n) kroků. Jelikož uděláme n kroků.
Příklad:
Máme rybník, kde máme 15 kamennů přes který se máme dostat, tudiž nám to zabere 15 kroků. Tedy O(15) kroků.
Kdybychom ovšem chtěli při každém kroku skočit tak se nám přidá ke každému kroku ještě jedna operace, tedy O(2n) kroků.
Kdybychom chtěli při každém kroku skočit a ještě se otočit, tak se nám přidá ke každému kroku ještě dvě operace, tedy O(3n) kroků.
Tohle rychlý souhrn o co se jedná, mnohem lepší vysvtlení je na IT networku
O Omikron - vyjdařuje horní hranici, tedy nejhorší možný scénář.
Ω Omega - vyjadřuje dolní hranici, tedy nejlepší možný scénář.
Θ Theta - vyjadřuje průměrný scénář.
Kdybychom měli projet všechny prvky v poli, které má n prvků, tak nám to zabere O(n) kroků. Jelikož uděláme n kroků.
Příklad:
Máme rybník, kde máme 15 kamennů přes který se máme dostat, tudiž nám to zabere 15 kroků. Tedy O(15) kroků.
Kdybychom ovšem chtěli při každém kroku skočit tak se nám přidá ke každému kroku ještě jedna operace, tedy O(2n) kroků.
Kdybychom chtěli při každém kroku skočit a ještě se otočit, tak se nám přidá ke každému kroku ještě dvě operace, tedy O(3n) kroků.
Tohle rychlý souhrn o co se jedná, mnohem lepší vysvtlení je na IT networku
O Ω Θ
Výpočet asymptotické složitosti
Každý algorimus má 3 časové složitosti které vyjadřují jejich třídní chování (průměrné), horní hranici (nejhorší), dolní hranici (nejlepší)
O Omikron - vyjdařuje horní hranici, tedy nejhorší možný scénář.
Ω Omega - vyjadřuje dolní hranici, tedy nejlepší možný scénář.
Θ Theta - vyjadřuje průměrný scénář.
Prostorová(paměťová) složitost algoritmů
Jedná se o to, kolik paměti algoritmus potřebuje. Tedy kolik paměti zabere.
Značí se jako S(n), kde n udává maximální množství paměti použité strojem při výpočtech nad vstupy velikosti n.
Prostorová složitost může být mnohdy o dost menší než časová složitost. Například u Insertion sortu je Θ(n), zatímco časová složitost je Θ(n²).
Značí se jako S(n), kde n udává maximální množství paměti použité strojem při výpočtech nad vstupy velikosti n.
Prostorová složitost může být mnohdy o dost menší než časová složitost. Například u Insertion sortu je Θ(n), zatímco časová složitost je Θ(n²).
Algoritmy v poli
Zde jsou napsaný ty nejlehčí algoritmy, které se dají použít na pole.
-
public static int FindMax(int[] numbers) { if (numbers == null || numbers.Length == 0) { throw new ArgumentException("The array must not be null or empty."); } // Vytvoři si pomocnou proměnnou, která bude uchovávat maximální hodnotu int max = numbers[0]; // Projed celé pole for (int i = 1; i < numbers.Length; i++) { // Porovnej každý prvek s aktuálním maximem if (numbers[i] > max) { // Vyměn maximální hodnotu, pokud je aktuální prvek větší max = numbers[i]; } } return max; } public static int FindMax(int[] numbers) { if (numbers == null || numbers.Length == 0) { throw new ArgumentException("The array must not be null or empty."); } // Vytvoři si pomocnou proměnnou, která bude uchovávat minimalní hodnotu int min = numbers[0]; // Projed celé pole for (int i = 1; i < numbers.Length; i++) { // Porovnej každý prvek s aktuálním minimem if (numbers[i] < min) { // Vyměn minimalní hodnotu, pokud je aktuální prvek menší min = numbers[i]; } } return min; }
-
public static void ReverseArray(int[] arr) { if (arr == null || arr.Length == 0) { throw new ArgumentException("The array must not be null or empty."); } int left = 0; int right = arr.Length - 1; while (left < right) { // Vyměn prvka zleva a zprava int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; // Pohni se na další prvek left++; right--; } }
-
public static int[] Insert(int[] arr, int element, int index) { if (index < 0 || index > arr.Length) { throw new ArgumentOutOfRangeException(nameof(index), "Index is out of range."); } int[] newArray = new int[arr.Length + 1]; for (int i = 0, j = 0; i < newArray.Length; i++) { if (i == index) { newArray[i] = element; } else { newArray[i] = arr[j]; j++; } } return newArray; }
-
static int LinearSearch(int[] arr, int target) { for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) { return i; // Vrací číslo indexu pokud je nalezen } } return -1; // Vrací -1 pokud není nalezen }
-
static int BinarySearch(int[] arr, int target) { int left = 0; int right = arr.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; // Koukne se zda je na středu if (arr[mid] == target) { return mid; } // Pokud je cil větší jak prava tak ignoruje levou polovinu if (arr[mid] < target) { left = mid + 1; } else // Pokud je cil menší tak ignoruje pravou polovinu { right = mid - 1; } } // Pokud se dostane až sem, znamená to že prvek nebyl nalezen return -1; }
Po rozkliknuti se zobrazí kód
Řadící algoritmy
Řadící algoritmy slouží jak z názvu napovída na řazení algoritmů. Algoritmu je hodně a každý má jiné vlastnosti. U každého určujeme:
- Časovou složitost
- Omikron
- Omega
- Theta
- Stabilitu
- Na místě
Název | Omikron | Omega | Theta | O | Ω | Θ | Stabilní | Stb. | Na místě | nms. | |
---|---|---|---|---|---|---|---|---|---|---|---|
Bubble sort | n² | n | n² | ✅ | ✅ | Více.. | |||||
Selection sort | Sel. sort | n² | n² | n² | 🚫 | ✅ | Více.. | ||||
Insertion sort | Ins. sort | n² | n | n² | ✅ | ✅ | Více.. | ||||
Quick sort | n² | n log n | n² | 🚫 | ✅ | Více.. | |||||
Merge sort | n log n | n log n | n log n | ✅ | 🚫 | Více.. | |||||
Heap sort | n log n | n log n | n log n | 🚫 | ✅ | Více.. |