Algoritma Analizi - O(1) - Constant

Giriş
O(n) ile O(1)'in farkını gösteren bir şekil şöyle. Burada yürüme mesafesi arttıkça yürüme süresi de artıyor dolayısıyla O(n), ancak ışınlanma mesafeden bağımsız hep O(1)

              Walk
  time |       /
       |      /
60 secs+-----+--------------------------- Teleport
       |    /
       |   /
       |  /
       | /
       |/
       +--------------------------------
               PROBLEM SIZE N = DISTANCE

Bu şekle bakarak + işareti ile belirtilen mesafeye kadar O(n) ışınlanmaya tercih edilebilir. Eğer şekil şöyle olsaydı + ile belirtilen mesafe daha da kısa olacaktı.

           Walk
  time |    /
       |   /
60 secs+--+----------------------------- Teleport
       | /
       |/
30 secs+   Putting on shoes in 30 seconds
       |
       |
       +--------------------------------
               PROBLEM SIZE N = DISTANCE

Eğer şekil şöyle olsaydı O(n) her zaman O(1)'den daha maliyetli olduğu için tercih edilmezdi.

        Walk
  time | /
       |/
90 secs+   Putting on shoes in 90 seconds
       |
       |
60 secs+-------------------------------- Teleport
       |
       |
30 secs|
       |
       |
       +--------------------------------
               PROBLEM SIZE N = DISTANCE

Array
Verilen index'e erişimin maliyeti O(1)'dir. Array'e ekleme ve silme işlemlerinin maliyetleri daha farklıdır. En kötü ihtimalle O(n)'dir.

Sıralanmış Liste
Örneğin küçükten büyüğe sıralanmış olan bir listede en küçük elemanın maliyeti O(1)'dir.

Singly Linked List
Böyle bir listenin en başına bir eleman eklemenin maliyeti O(1)'dir.

HashMap (Java) / std::unordered_map (C++)
Aslında mükemmel hash fonksiyonu olmadığı için anahtarların çakışması durumundan kaçınmak mümkün değildir.
Çakışmalar yüzünden her hash kullanan veri yapısında bir miktar O(1)'den fazla işlem yapar ancak Amortized Analysis yöntemince zamana yayılan kullanımda limiti alınan denklem sonsuzda O(1)' yakınsar. Bu yüzden O(1) kabul edilir. Amortized algortimaları anlamak için buradaki cümle önemli:

Amortized algorithms and data structures usually perform additional house keeping tasks which "amortize" for the performance costs of other operations.

Yine buradaki cevapta veriyapısının boyunun değişmesi gereken durumda elemanların hash değerinin tekrar hesaplanarak yeni yerlerine yerleştirildiği, dolayısıyla O(n) bir işlem yapıldığı anlatılıyor.

Döngüler
Döngü içi içe olsa bile, dönüş sayısı sabit ise maliyeti O(1)'dir.

for i in [1.. 10^15]:
    for j in [1.. 10^15]:
        for k in [1.. 10^15]:
            dosomethingO1()