--- title: Big-O Notasyonu slug: big-o-notasyonu-c10a5 url: /detay/big-o-notasyonu-c10a5 type: article language: Türkçe entity: primary: Big-O Notasyonu type: article disambiguation: Algoritma verimliliğini ölçen Big-O Notasyonu'nun temel tanımını, özelliklerini ve örneklerini öğrenin. Karmaşıklık analizinde olmazsa olmaz! categories: - name: Matematik slug: matematik url: /kategori/matematik - name: Makine, Robotik Ve Mekatronik slug: makine-robotik-ve-mekatronik url: /kategori/makine-robotik-ve-mekatronik - name: Bilişim Ve İletişim Teknolojileri slug: bilisim-ve-iletisim-teknolojileri url: /kategori/bilisim-ve-iletisim-teknolojileri tags: - Hesaplama Teorisi - Algoritma Anlamı - Asimptotik Analiz - Big-O Notasyonu - Karmaşıklık author: Beyza Nur Türkü created_at: 2025-07-10T01:02:25.781965+03:00 updated_at: 2025-07-22T23:57:42.031983+03:00 image: https://cdn.t3pedia.org/media/uploads/2025/07/09/d8SCQKfJSY2YdgUuyc05ab8y1qIUz1HQ.png --- # Big-O Notasyonu ## Article Content **Büyük O Notasyonu (Big-O Notation)**, bilgisayar bilimlerinde [algoritmaların](/tr/detay/algoritma-6/llms.txt) verimliliğini ölçmek için kullanılan temel asimptotik analiz araçlarından biridir. Bu notasyon, bir [algoritmanın çalışma süresinin](/tr/detay/verimli-algoritma-tasarimi-ve-optimizasyon-teknikl/llms.txt) veya bellek kullanımının, girdi boyutuna bağlı olarak ne şekilde büyüdüğünü teorik bir çerçevede ifade eder. *Big-O*, belirli bir fonksiyonun üst sınırını tanımlamak amacıyla kullanılır ve bu yönüyle algoritmaların karmaşıklık analizinde temel bir ölçü birimi hâline gelmiştir. Terim, Almanca *Ordnung* (sıra, düzen) kelimesinden türetilmiş olup 1894 yılında Paul Bachmann tarafından “Analytische Zahlentheorie” isimli eserinde tanıtılmıştır. [Donald Knuth](/tr/detay/donald-knuth-0036f/llms.txt)’un bu kavramı sistematik olarak bilgisayar bilimine kazandırmasıyla modern algoritma analizinin vazgeçilmez bir unsuru olmuştur. ### **Büyük O Notasyonunun Temel Tanımı** Bir fonksiyon *f(n)*, başka bir fonksiyon *g(n)* cinsinden *Büyük O* notasyonu ile ifade edildiğinde, *f(n) = O(g(n))* şeklinde gösterilir. Bu ifade, *f(n)* fonksiyonunun *g(n)* fonksiyonunun sabit bir katından büyük olamayacağını söyler. Daha resmi tanımıyla: **Tanım: ***f(n) = O(g(n))* ise ve ancak ancak pozitif sabitler *c* ve *k* var ise: $0 \leq f(n) \leq c * g(n), \forall n \geq k$ Burada *c* ve *k* sabitleri sabittir ve *n*'ye bağlı değildir. Bu tanım, *Big-O* kavramının temel amacını ortaya koyar: Algoritmanın en kötü durumda nasıl davrandığını anlamak. #### **Asimptotik Üst Sınır** Büyük O Notasyonu’nun temel işlevi, algoritmaların çalışma süresi veya bellek gereksiniminin giriş boyutuna bağlı olarak nasıl büyüdüğünü göstermektir. Bu bağlamda, *asimptotik üst sınır* kavramı, bir algoritmanın performansının en kötü durumda alabileceği maksimum değeri temsil eder. Bu, algoritmanın pratikte her zaman bu süreyi harcayacağı anlamına gelmez; ancak en olumsuz senaryoda bile belirli bir üst sınırın aşılmayacağını garanti eder. Formel olarak, bir fonksiyon *f(n)* için [asimptotik üst sınır](/tr/detay/asimptot-02122/llms.txt) şöyle ifade edilir: $f(n) = O(g(n)) => \exists c > 0, \exists k \geq 0, \forall n \geq k : 0 \leq f(n) \leq c * g(n)$ Buradaki *g(n)*, karşılaştırma fonksiyonu olup, *f(n)* fonksiyonunun büyüme hızını kontrol altında tutacak referans değeridir. Sabit *c* ve başlangıç noktası *k*, yalnızca *f* ve *g* fonksiyonlarına bağlıdır, *n*’ye bağlı değildir. Böylece analiz, donanıma, dile veya derleyiciye bağlı olmaksızın algoritmanın temel büyüme eğilimini ortaya koyar. #### **Büyük O’nun Özellikleri** [Big-O notasyonunun](/tr/detay/big-o-notation-67402/llms.txt) kuramsal gücü, bazı temel özellikleri sayesinde sağlam temellere oturur: ##### **Yansıma (Reflexivity)** Her fonksiyon kendisiyle aynı sınıfa dahildir: $f(n) = O(f(n))$ ##### **Aktarım (Transitivity)** Büyüme sınıfları zincirleme aktarılabilir: $f(n) = O(g(n)), g(n) = O(h(n)) => f(n) = O(h(n))$ ##### **Sabit Çarpan Kuralı** Sabitler asimptotik büyümeyi etkilemez: $f(n) = O(g(n)) => c * f(n) = O(g(n)), c>0$ ##### **Toplama Kuralı** $f(n)=O(h(n)),g(n)=O(k(n))⟹f(n)+g(n)=O(max{h(n),k(n)})$ ##### **Çarpma Kuralı** $f(n)=O(h(n)),g(n)=O(k(n))⟹f(n)⋅g(n)=O(h(n)⋅k(n))$ ### **Algoritma Karmaşıklıkları** Bir algoritmanın karmaşıklığı genelde giriş boyutu *n* cinsinden ifade edilir. Bazı yaygın sınıflar şunlardır: - **O(1)**: Sabit zaman — örn. bir diziye indeksle erişim. - **O(log n)**: Logaritmik — örn. binary search. - **O(n)**: Doğrusal — örn. lineer arama. - **O(n log n)**: Log-lineer — örn. merge sort. - **O(n²)**: Karesel — örn. bubble sort. - **O(2ⁿ)**: Üssel — örn. alt küme üretme. - **O(n!)**: Faktöriyel — örn. tüm permütasyonları üretme. #### **Hesaplamalı Karmaşıklık Teorisi ile İlişkisi** Big-O Notasyonu, hesaplamalı karmaşıklık teorisinin de temelidir. P ve NP sınıfları, polinom zamanda çözülebilirlik (O(n^c)) veya üssel/faktöriyel zaman (O(2ⁿ), O(n!)) gibi sınıflar üzerinden tanımlanır. Bir algoritmanın polinom zamanda çalışması (*O(n^k)*) genelde uygulanabilirlik ölçütü olarak kabul edilir. Aksi hâlde problem *NP-Zor* ya da *NP-Tam* olarak sınıflandırılabilir. #### **Asimptotik Davranışın Sınırları: Otomat Teorisi Örneği** Kaynak metinlerinde Big-O ve Big-Θ kavramlarının otomata kuramındaki özel kullanımları da tartışılmıştır. Bazı ağırlıklı otomatlarda, bir durumu Big-O cinsinden test etmek, Big-Θ’ya dönüştürülebilir. Cook ve Karp indirgemeleri, bir karar probleminin başka bir problem üzerinden çözülebileceğini gösterir. Ayrıca “Eventually Big-O” kavramı, sonsuz uzunlukta sözcüklerde Big-O sınırlarının sağlanması gerektiğini belirtir. Bazı semiringlerde (örneğin tropikal semiring) bu tür kapsama problemleri karara bağlanabilirken, bazılarında kararsız (undecidable) olabilir.$0 \leq f(n) \leq c * g(n), \forall n \geq k$ ## Academic Sources and References 1. Chistikov, Dmitry, Stefan Kiefer, Andrzej S. Murawski, and David Purser. "The big-O problem." Logical Methods in Computer Science 18 (2022). Erişim Adresi. 2. Danziger, P. "Big o notation." Source internet: http://www. scs. ryerson. ca/mth110/Handouts/PD/bigO. pdf, Retrieve: April 1, no. 1 (2010): 6. Erişim Adresi. 3. Geeksforgeeks. "Big O Notation Tutorial - A Guide to Big O Analysis". 2025. Erişim Tarihi: 14 Temmuz 2025. Erişim Adresi. 4. National Institute of Standards and Technology. "Big-O Notation". Erişim Tarihi: 14 Temmuz 2025. Erişim Adresi.