Junior
Listen içindeki öğelerle yapılan işlemlerin asimptotik karmaşıklığı nedir?
sobes.tech yapay zeka
AI'dan gelen yanıt
Liste tipi ve işlemin türüne bağlıdır.
Genellikle aşağıdaki liste türleri dikkate alınır:
- Tek yönlü bağlı liste
- Çift yönlü bağlı liste
- Dizi (liste durumunun özel bir örneği)
İşlemler:
- İndeksle erişim
- Ekleme
- Silme
- Değer arama
| İşlem | Tek yönlü bağlı liste | Çift yönlü bağlı liste | Dizi |
|---|---|---|---|
| İndeksle erişim | O(n) | O(n) | O(1) |
| Ekleme | O(1) (başlangıca) | O(1) (başlangıç/son) | O(n) |
| Silme | O(n) | O(n) | O(n) |
| Değer arama | O(n) | O(n) | O(n) |
Açıklamalar:
- O(1) (Sabit zaman): İşlem, listenin boyutundan bağımsız olarak sabit bir zaman alır. Örneğin, dizide indeksle elemana erişim.
- O(n) (Doğrusal zaman): İşlemin çalışma süresi, listenin boyutuyla doğru orantılıdır. Örneğin, sıralanmamış bir listede öğe arama.
- O(log n) (Logaritmik zaman): İşlem süresi, listenin boyutuyla logaritmik olarak artar. Sıralı verilerle çalışırken sıkça görülür (örneğin, ikili arama).
Detaylar:
- Tek yönlü bağlı listede: Başlangıca ekleme - O(1). Son veya indeksle ekleme/silme, istenen elemana kadar listeyi dolaşmayı gerektirir, bu da O(n) olur.
- Çift yönlü bağlı listede: Başlangıca ve sona ekleme - O(1). Belirli bir konuma ekleme/silme - O(1), ancak bu düğümü değer veya indeksle bulmak - O(n).
- Dizide: İndeksle erişim - O(1). Ortadaki öğeye ekleme veya silme, öğeleri kaydırmayı gerektirir, bu da O(n) olur. Sonuna ekleme/silme, yeterli kapasite varsa (örneğin,
std::vector'de belirli bir kapasiteyle), ortalama O(1) olabilir, en kötü durumda (yeniden tahsis) O(n).