1 00
 |
Hesaplama karmaşıklığı (computational complexity) nedir? |
Bir algoritmanın hesaplama karmaşıklığı, algoritmanın çalışması için gerekli süreyi ya da bellek alanını göstermek için kullanılan kavramdır.
Tanım
Hesaplama karmaşıklığı (computational complexity), bir algoritmanın çalışması için gerekli kaynakların miktarıdır. Bu terim algoritma karmaşıklığı (complexity of an algorithm) olarak da bilinir.
Büyüme hızı
Bir algoritmanın, çalışma süresinin belirli bir değişkene bağlı olarak artmasına büyüme hızı denir.
Analiz
Algoritma analizi yapılırken genellikle az sayıdaki girdi ile değil, girdilerin büyüyerek sonsuza gittiği durumda kaynak kullanımının büyüme fonksiyonu ile ilgilenilir. Bu nedenle asimptotik analiz kullanılır.
Gösterim
Bir problemin karmaşıklığı, yani ihtiyaç duyduğu kaynaklar, giriş (input) miktarı (n) ile değişiklik gösterir. Bu yüzden karmaşıklık genellikle n'nin bir fonksiyonu olarak gösterilir.
T(n)
T(n) büyüme fonksiyonu, o algoritmanın hesaplama karmaşıklığıdır. Daha özel bir ifade ile zaman karmaşıklığıdır.
Türleri
İki tür hesaplama karmaşıklığı vardır. Bunlar bilgisayar biliminde önemi iki kaynaktır:
Çözümü oluşturan algoritma adımlarının çalışması için geçen süreyi veren bağıntıya zaman karmaşıklığı denir.
Alan karmaşıklığı
Çözümü oluşturan algoritma adımlarının çalışması için gerekli bellek miktarını gösteren bağıntıya alan karmaşıklığı denir.
Hesaplama karmaşıklığı (computational complexity), bir algoritmanın çalışması için gerekli kaynakların miktarıdır. Bu terim algoritma karmaşıklığı (complexity of an algorithm) olarak da bilinir.
Büyüme hızı
Bir algoritmanın, çalışma süresinin belirli bir değişkene bağlı olarak artmasına büyüme hızı denir.
Analiz
Algoritma analizi yapılırken genellikle az sayıdaki girdi ile değil, girdilerin büyüyerek sonsuza gittiği durumda kaynak kullanımının büyüme fonksiyonu ile ilgilenilir. Bu nedenle asimptotik analiz kullanılır.
Gösterim
Bir problemin karmaşıklığı, yani ihtiyaç duyduğu kaynaklar, giriş (input) miktarı (n) ile değişiklik gösterir. Bu yüzden karmaşıklık genellikle n'nin bir fonksiyonu olarak gösterilir.
| n → f(n) |
T(n)
T(n) büyüme fonksiyonu, o algoritmanın hesaplama karmaşıklığıdır. Daha özel bir ifade ile zaman karmaşıklığıdır.
Türleri
İki tür hesaplama karmaşıklığı vardır. Bunlar bilgisayar biliminde önemi iki kaynaktır:
- zaman karmaşıklığı (time complexity): zaman maliyeti
- alan karmaşıklığı (space complexity): alan maliyeti
Çözümü oluşturan algoritma adımlarının çalışması için geçen süreyi veren bağıntıya zaman karmaşıklığı denir.
Alan karmaşıklığı
Çözümü oluşturan algoritma adımlarının çalışması için gerekli bellek miktarını gösteren bağıntıya alan karmaşıklığı denir.
Bu alana not ekleyebilirsiniz.
Başka bir sorunuz mu var?
Yorumlar (0)
Henüz yorum yapılmamış.
