Programování
Algoritmy
Co je to algoritmus?
Algoritmus je pracovní postup, který má tyto povinné vlastnosti.
  1. Rezultativnost.
    To znamená, že vždy vydá nějaký výsledek.
  2. Finitnost (konečnost).
    To znamená, že někdy skončí. Jinými slovy, skončí po konečném počtu provedených kroků.
  3. 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).
  4. 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.
Když se na to podíváme z lidského pohledu, algoritmus by mohl být třeba návod, jak ráno vstát. I když to zní jednoduše, je to docela problém. Počítače jsou totiž stroje a ty nemyslí. Musíme tedy dopodrobna popsat všechny kroky algoritmu.
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
Algoritmy jdou zapsat v různých jazycích, například v jazyce C#, Python, Java, C++ a dalších. Jeden algoritmus může být napsán v různých jazycích. Ovšem jejich vnitřní fungovaní není vždy stejné
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 Ω Θ
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²).
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ě
Základní řadící algoritmy jsou:
Název Omikron Omega Theta O Ω Θ Stabilní Stb. Na místě nms.
Bubble sort n Více..
Selection sort Sel. sort 🚫 Více..
Insertion sort Ins. sort n Více..
Quick sort n log 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..