Algoritma Analizi - O(log(n)) - Logaritmic

Giriş
O(log(n)) bir problemi daha küçük parçalara ayırarak çözme anlamına geliyor. Logaritmik algoritmaların genel özellikleri şöyle olur

1. Algoritmanın önünde bir çok seçenek olur.
2. Sadece bir tanesi seçilir.

- O(log(n)), O(n)'den daha iyidir. Karşılaştırmayı şöyle görebilirsiniz. Grafiği ise şöyle.

- O(log(n)), O(1) ile karşılaştırılınca sanki kulağa verimsizmiş gibi gelse de küçük sayılar için O(1) ve 

O(log(n) arasında çok az fark vardır.

Örnek

Bir denklemi şöyle yazabiliriz.

O(log n/2) = O( (log n) + log(1/2))

Sabiti dikkate almazsak şöyle olur

O(log n / 2) = O(log n)

Örnek - log4 hesaplama

log4 tabanında n'i hesaplayan bir kod şöyle.

int foo (int n) 
{
  m = 0;
  while (n >= 2)
  {
    n = n / 4;
    m = m + 1;
  }   
  return m;
 }

Örnek - Exponentiation by squaring
İsmi cafcaflı olsa da "Exponantiation by squaring" aslında pow metodudur.
Çözüm  1
Şöyle yaparız. Üssü sayısı tek ise a ile bir kere daha çarpılır. Çift ise pow (2,8) aslında pow (2,4) * pow (2,4)'e eşittir.

int pow(int a, int n) {
  if (n == 0) return 1;

  int halfPow = pow(a, n / 2);
  if (n % 2 == 0) return halfPow * halfPow;
  else return halfPow * halfPow * a;
}

Çözüm 2
Şöyle yaparız.

unsigned long long power(unsigned n, unsigned p)
{
  unsigned long long x=1, y=n;
  while(p > 0)
  {
    if(p&1) x *= y;
    y *= y;
    p >>= 1;
  }
  return x;
}

Not : pow metodunun tersi "nth root" işlemidir. Formülü şöyle

Math.pow(number, 1/nth root)

Ya da Newton metodu kullanılabilir. Şöyle yaparız.

function iroot(k, n)
  k1 := k - 1
  s := n + 1
  u := n
  while u < s
    s := u
    u := ((u * k1) + n // (u ** k1)) // k
  return s

Çağırmak için şöyle yaparız. Sonuç olarak 5 alırız.

iroot(4, 625)

Örnek  - Binary Search

Klasik Binary Search şöyledir.

var first = 0;
var last = 10000;
while (first+1 < last) {
  var mid = (first+last)/2;
  if (string.IsNullOrEmpty(myWorksheet.Cells[mid, 1].Text)) {
    last = mid;
  } else {
    first = mid;
  }
}

1. Veri Yapısı
Binary search O(log(n))'dir. Ancak burada unutulmaması gereken nokta binary search yapabilmek için veri yapısına erişim yeteneğinin O(1) olması gerekir.

İşte bu yüzden Java'da Arrays.binarySearch() metodu O(log(n)) performası garanti eder.

Collections.binarySearch() metodu ise açıklamasında eğer O(1) arama imkanı tanıyan bir liste kullanılırsa O(log(n)) performası garanti edeceğini, eğer kullanılmazsa O(n) * O(log(n)) performansı vereceğini söylüyor.

Örnek - Binary Search ve Priority Queue

Elimizde bir toplantı dizisi olsun. Çakışan toplantıları bulmak isteyelim. Şöyle yaparız. Burada önce toplantılar başlama saatine göre sıralanıyor. Daha sonra bitiş saati başlama saatinden küçükse yani çakışma yoksa, Priority Queue'dan siliniyor. Priority Queue kullanıldığı için O(n∗log(n)). O da O(n) yapar.

public static int minMeetingRooms(int[][] meetingTimes){
        
  if(meetingTimes.length == 0){
    return 0;
  }
  //Sort by start time
  Arrays.sort(meetingTimes, (a, b) -> Integer.compare(a[0], b[0]));       

  //min Heap keeps track of earliest ending meeting:
  PriorityQueue<Integer> minHeap = new PriorityQueue<>((A, B) -> A - B);
        
  minHeap.add(meetingTimes[0][1]);
        
  for (int i = 1; i < meetingTimes.length; i++) {
    int currStart = meetingTimes[i][0];
    int currEnding = meetingTimes[i][1];
    int earliestEnding = minHeap.peek();

    //If two meetings do not overlap remove the meeting in PriorityQueue
    //because we don't need a seperate room
    if (earliestEnding <= currStart) {
      minHeap.remove();
    } 
    //update heap with curr ending
    minHeap.add(currEnding);
  }
  return minHeap.size();
}

2-  Karşılatırma İşlemi- Comparison
O(log(n)) için iki nesnesi karşılatırma işleminin O(1) olduğu varsayılır. Eğer karşılaştırma işlemi O(M) ise O(M * log(n)) elde ederiz.

3 Jump Search
Binary search'ün ileri ve geri atmala yapabilmeye dayanır. Geri atlama yapılamayan durumda jump search kullanılabilir. Açıklaması şöyle

The use case for jump search (O(√n)) over binary search (O(log n)) is when jumping back is expensive. Replacing the linear search in jump search would be counterproductive in that regard.

Örnek - Binary Search Problemi
"Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne" kitabındaki soru şöyle. N katlı binadan atılan yumurta F katından itibaren kırılmaya başlıyor. log (N) denemede kaçıncı katta kırıldığımı bulmak gerekiyor. Tabi elimizde yeterli yumurta olduğu varsayılıyor. Tek bir yumurta olsaydı ve kırılsaydı bir daha deneme yapamazdık :)

Presume that we have a story building with N-floors, and presume that an egg will break if you drop it from floor F(F ≤ N) or higher, but the egg will NOT break if you drop it from any floor lower than this. We know the value of N, and now we are going to figure out the value of F.

a.) Presume that we have loads of eggs to try this out with. Think of a strategy to figure out F by crushing ∼ lg N eggs.

Örnek  - Binary Insert
Özyinelemeli olarak şöyle yaparız.

Node* insert(Node*& root, int key, int value) {
  if (!root) 
    root = new Node(key, value);
  else if (key < root->key)
    root->left = insert(root->left, key, value);
  else  // key >= root->key
    root->right = insert(root->right, key, value);
  return root;
}

Örnek  - Binary Tree
Binary Tree yazısına taşıdım.