Zbiory - operacje na zbiorach

1. Czym jest zbiór?

Zbiór (set) to nieuporządkowana kolekcja unikalnych elementów. Bazuje na matematycznym pojęciu zbioru.

Kluczowe cechy zbioru:

  • Nieuporządkowany – elementy nie mają określonej kolejności.
  • Unikalne elementy – każdy element występuje tylko raz.
  • Mutowalny – można dodawać i usuwać elementy.
  • Elementy hashowalne – mogą być tylko niemutowalne obiekty.
  • Szybkie operacje – wyszukiwanie, dodawanie, usuwanie w O(1).

2. Tworzenie zbiorów

2.1. Podstawowa składnia

2.2. Konstruktor set()

2.3. Set comprehension

3. Dodawanie elementów

3.1. add() – dodaj pojedynczy element

Złożoność czasowa: O(1)

3.2. update() – dodaj wiele elementów

Złożoność czasowa: O(k), gdzie k to liczba elementów do dodania.

4. Usuwanie elementów

4.1. remove() – usuń element (błąd jeśli nie istnieje)

Złożoność czasowa: O(1)

4.2. discard() – usuń element (bez błędu)

Złożoność czasowa: O(1)

4.3. pop() – usuń losowy element

Uwaga: Kolejność jest nieprzewidywalna!

4.4. clear() – usuń wszystkie elementy

5. Sprawdzanie przynależności

5.1. Operator in

Złożoność czasowa: O(1) – znacznie szybciej niż w liście!

5.2. Porównanie z listą

6. Operacje na zbiorach

6.1. Suma zbiorów (union) – | lub union()

Zwraca zbiór zawierający wszystkie elementy z obu zbiorów.

Złożoność czasowa: O(len(A) + len(B))

6.2. Przecięcie zbiorów (intersection) – & lub intersection()

Zwraca zbiór zawierający tylko wspólne elementy.

Złożoność czasowa: O(min(len(A), len(B)))

6.3. Różnica zbiorów (difference) – - lub difference()

Zwraca elementy z A, które nie są w B.

Złożoność czasowa: O(len(A))

6.4. Różnica symetryczna (symmetric difference) – ^ lub symmetric_difference()

Zwraca elementy, które są w A lub B, ale nie w obu.

Złożoność czasowa: O(len(A) + len(B))

7. Operacje z modyfikacją (in-place)

7.1. update() lub |= – dodaj elementy z innego zbioru

7.2. intersection_update() lub &=

7.3. difference_update() lub -=

7.4. symmetric_difference_update() lub ^=

8. Relacje między zbiorami

8.1. Podzbiór (subset) – <= lub issubset()

Sprawdza, czy A jest podzbiorem B (wszystkie elementy A są w B).

8.2. Nadzbiór (superset) – >= lub issuperset()

Sprawdza, czy A jest nadzbiorem B (wszystkie elementy B są w A).

8.3. Zbiory rozłączne – isdisjoint()

Sprawdza, czy zbiory nie mają wspólnych elementów.

9. Inne operacje

9.1. len() – liczba elementów

Złożoność czasowa: O(1)

9.2. copy() – kopia zbioru

10. Iterowanie po zbiorze

10.1. Pętla for

10.2. Set comprehension

11. frozenset – niemutowalny zbiór

Frozenset to niemutowalna wersja zbioru. Może być kluczem w słowniku lub elementem zbioru.

11.1. Tworzenie frozenset

11.2. Frozenset jako klucz słownika

11.3. Frozenset w zbiorze

12. Praktyczne zastosowania

12.1. Usuwanie duplikatów

12.2. Sprawdzanie czy listy mają wspólne elementy

12.3. Znajdowanie unikalnych słów w tekście

12.4. Sprawdzanie czy wszystkie elementy są unikalne

12.5. Filtrowanie na podstawie drugiej listy

13. Złożoność czasowa operacji na zbiorach

Operacja Średnia Najgorszy
x in zbior O(1) O(n)
zbior.add(x) O(1) O(n)
zbior.remove(x) O(1) O(n)
zbior.discard(x) O(1) O(n)
A | B (union) O(len(A) + len(B))
A & B (intersection) O(min(len(A), len(B)))
A - B (difference) O(len(A))
len(zbior) O(1) O(1)

14. Zbiory w matematyce – przykłady

14.1. Teoria zbiorów

14.2. Prawa De Morgana

15. Najczęstsze błędy

Błąd 1: Próba dodania niehashowalne obiektu

Błąd 2: Pusty zbiór vs pusty słownik

Błąd 3: Modyfikacja zbioru podczas iteracji

16. Zbiór vs Lista vs Słownik

Cecha Zbiór Lista Słownik
Uporządkowana Nie Tak Tak (3.7+)
Duplikaty Nie Tak Klucze unikalne
Wyszukiwanie O(1) O(n) O(1)
Indeksowanie Nie Tak Po kluczu
Modyfikowalna Tak Tak Tak
Użycie pamięci Średnie Małe Duże

17. Podsumowanie

Zbiory to potężna struktura danych do pracy z unikalnymi elementami:

  • Szybkie wyszukiwanie: O(1)
  • Automatyczne usuwanie duplikatów
  • Operacje matematyczne (suma, przecięcie, różnica)
  • Idealne do sprawdzania przynależności

Kluczowe operacje:

  • add(), remove(), discard() – modyfikacja
  • |, &, -, ^ – operacje na zbiorach
  • in – sprawdzanie przynależności (O(1)!)

Kiedy używać zbiorów?

  • Potrzebujesz unikalnych elementów
  • Chcesz szybko sprawdzać przynależność
  • Wykonujesz operacje matematyczne na zbiorach
  • Musisz usunąć duplikaty

Co dalej warto poznać:

  • frozenset – niemutowalny zbiór
  • Algorytmy grafowe (zbiory wierzchołków)
  • Optymalizacja zapytań do bazy danych
  • Teoria zbiorów w matematyce
Wróć do spisu lekcji