Algorytmy 3

Front

Co to jest sortowanie przez scalanie (merge sort)?

Back

To strategia sortowania, która dzieli listę na połowy, rekurencyjnie sortuje każdą połowę, a następnie scala dwie posortowane podlisty.

Front

Jak działa algorytm Merge w sortowaniu przez scalanie?

Back

Algorytm Merge przyjmuje dwie uporządkowane tablice A i B, porównuje ich elementy i tworzy nową tablicę e, która zawiera wszystkie elementy A i B w porządku rosnącym.

Front

Jakie jest złożoność czasowa algorytmu Merge?

Back

Złożoność czasowa algorytmu Merge wynosi O(n + m), gdzie n i m to długości tablic A i B.

Front

Jak działa funkcja mergesort?

Back

Funkcja mergesort dzieli tablicę na dwie części, rekurencyjnie sortuje każdą z nich, a następnie scala wyniki za pomocą funkcji Merge.

Front

Jakie jest ogólne złożoność czasowa algorytmu mergesort?

Back

Złożoność czasowa algorytmu mergesort wynosi O(n log n).

Front

Co to jest heapsort?

Back

Heapsort to algorytm sortowania, który działa w miejscu i wykorzystuje strukturę danych zwaną kopcem.

Front

Jakie są podstawowe procedury działające na kopcach?

Back

Podstawowe procedury to Heapify, Build-Heap i Heapsort.

Front

Jakie jest znaczenie procedury Heapify?

Back

Heapify przywraca własność kopca, zapewniając, że dla każdego węzła i, jego wartość jest nie większa niż wartość jego rodzica.

Front

Jak działa procedura Build-Heap?

Back

Build-Heap przekształca nieuporządkowaną tablicę w kopiec, wywołując Heapify dla każdego węzła od dołu do góry.

Front

Jakie jest złożoność czasowa procedury Build-Heap?

Back

Złożoność czasowa procedury Build-Heap wynosi O(n).