Algoritma Analizi - O(n2) - İkinci Dereceden Yani Quadratic

Giriş

En basit örneği iç içe iki tane döngüdür.

Örnek - complexity of two nested loops over different datasets

Elimizde şöyle bir kod olsun

for things in list_a {
  for things in list_b {
    if (list_a.thing relates to list_b.thing) go ping
  }
}

Açıklaması şöyle. İki listenin de büyüklüğü farklı olabilse dahi en kötü durum düşünüleceği için sonuç O(n * m) yerine O(n^2)  olarak söylenir

It'd be O(n*m) where the worst case is n = m or n*n thus O(n^2). We are interested in worst case run time for Big O. If the data sets sizes are different then it will still be in O(n^2) since we can't guarantee that, for example, the second dataset will be a logarithmic relation to the first. If we could, they wouldn't necessarily be independent. They might be but again, we are looking at worst case and O(n logn) is within O(n^2).

Örnek - complexity of two nested loops one has fixed size

Bu soru anagramları gruplama sorusu. Şöyle yaparız. Algoritma analizi O (n * 26)'dır. Yani aslında O(n)'dir. complexity of two nested loops over different datasets sorusu ile farkını göstermek için ekledim

Her string için harf frekansı hesaplanır. Yani abbccc için şunu gibidir #1#2#3#0#0#0...#0. Her anagram aynı string'i verecektir. Böylece string'ler gruplanır.

public static List<List<String>> groupTitles(String[] strs){
  if (strs.length == 0) 
    return new ArrayList<List<String>>();

  Map<String, List<String>> res = new HashMap<>();
  int[] count = new int[26];
  for (String s : strs) {
    Arrays.fill(count, 0);
    for (char c : s.toCharArray()){
      int index = c - 'a';
      count[index]++;
    }
    StringBuilder delimStr = new StringBuilder("");
    for (int i = 0; i < 26; i++) {
      delimStr.append('#');
      delimStr.append(count[i]);
    }
            
    String key = delimStr.toString();
    if (!res.containsKey(key)) 
      res.put(key, new ArrayList<String>());
            
    res.get(key).add(s);
  }
  return new ArrayList<List<String>>(res.values());
}

Kullanmak için şöyle yaparız. duel,dule,deul bir grup, speed,spede bir grup, cars ise tek başına bir grup olur

String titles[] = {"duel","dule","speed","spede","deul","cars"};
List<List<String>> grups = groupTitles(titles);

String query = "spede";
// Iterate over groups
for (List<String> group : groups) {
  if (group.contains(query))
    System.out.println(g);
}

Örnek

Elimizde şöyle bir kod olsun. Burada da ikinci döngü aslında sabit bir değere bakarak dönmüyor. Ancak yine de sonuç O(n^2)

int n = ...;
int x = 0;
for (int i = 0; i < n; ++i) {
  for (int i = j; j < n; ++j) {
    ++x;
  }
}

Selection Sort

Bu sıralama algoritmasında içteki döngü dıştaki sıralanmamış eleman ile karşılaştırma yaparak, en küçük elemanı bulur ve yer değiştirir. Örnek burada.

Bubble Sort
n² (n kare) arama için Bubble Sort güzel bir örnek. Bu algoritma yanyana bulunan çiftlerin karşılaştırılması şeklinde çalışıyor. Her bir eleman yanındaki ile yer değiştirmeye ihtiyaç duymayıncaya kadar tüm liste tekrar tekrar dolaşılıyor.

Algoritma Analizi - O (n) Linear - Diziyi Sağdan ve Soldan Başlayarak Dolaşma Two Pointers Technique

Giriş

Örnek

Soru şöyle

Problem Statement : Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.alo

Input: arr = [1, 2, 3, 4, 6], target=6

Output: [1, 3]

Explanation: The numbers at indices 1 and 3 add up to 6: 2+4=6

Açıklaması şöyle. Burada dizinin sıralı olması önemli

We will start with one pointer pointing to the beginning of the array and another pointing at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do, we have found our pair; otherwise, we will do one of two things:

1. If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.

2. If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.

Bir diğer çözüm şöyle. Burada array üzerinde dolaşılıyor ve array sıralı olmak zorunda değil

Instead of using a two-pointer, we can utilize a HashTable to search for the required pair. We can iterate through the array one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ such that “X + Y = Target”. We will do two things here:

1. Search for ‘Y’ (which is equivalent to “Target - X”) in the HashTable. If it is there, we have found the required pair.

2. Otherwise, insert “X” in the HashTable, so that we can search it for the later numbers.

Örnek

Soru şöyle. Burada ilk cevap 10 ve 14 arasındaki direklerin kaldırılması. İkinci cevap ise 16 ve 18 arasındaki direklerin kaldırılması

Given an integer array which represents the heights of adjacent vertical bars standing on the ground.

The width of each bar is 1. Now you have to pick two bars and remove the bars between them such that when rain falls the water collected between two bars is maximum. Note that the distance between bars remains the same after removing the remaining bars.

eg:
1. [10,5,6,12,14] ans: 30 (10*3)
2. [3 16 10 5 6 12 20 18] ans: 80 (16*(number of integers between 16 and 18)).

Çözüm şöyle

result := 0
left := 0
right := n - 1
while(left < right):
    result := max(result, (right - left - 1) * min(arr[left], arr[right]))
    if(arr[left] <= arr[right]):
        left := left + 1
    else:
        right := right - 1
    endif
end

Burada arr[left] <= arr [right] ise daha yüksek bir dirsek bulmak için solda indeks bir ilerletilir. Eğer sağ taraf kısa ise sağ taraf ilerletilir.

Algoritma Analizi - Big O Nedir?

Giriş
Big O işlenen eleman sayısı arttıkça, gerekli sürenin de ne kadar artacağını gösterir. Yani girdinin niceliği arttıkça algoritmanın ne kadar daha çok vakit aldığını anlamak için kullanırız.  Açıklaması şöyle.

Big-O Notation describes scalability
At its core, Big-O Notation is not a description of how long an algorithm takes to run. Nor is it a description of how many steps, lines of code, or comparisons an algorithm makes. It is most useful when used to describe how an algorithm scales with the number of inputs.

Big O belirtmek için söylenen cümleler şöyledir

The two phrases

- The running time is O(n2)

and

- The running time is at most O(n2)

mean the same thing.

Big O Sonucu

Bu değer her zaman artı bir değerdir. Açıklaması şöyle

running times of algorithms are positive integers

Benchmarking

Açıklaması şöyle. Yani sadece Big O'yu bulmak yeterli değil. Hala benchmarking gerekli.

Reading between the lines, I think you may be misunderstanding Big O analysis as being a replacement for benchmarking. It's not. An engineer still needs to benchmark their code if they want to know how fast it is. And indeed in the real world, an O(n) algorithm might be slower than an O(n2) algorithm on real-world data sets.

Asymptotic Kelimesi

Bazen Big O için yapılan açıklamalarda asymptotic kelimesi kullanılıyor. Asymptotic için açıklama şöyle.

When we look at input sizes large enough to make only the order of growth of the running time relevant, we are studying the asymptotic efficiency of algorithms.That is, we are concerned with how the running time of an algorithm increases with he size of the input in the limit, as the size of the input increases without bound. Usually, an algorithm that is asymptotically more efficient will be the best choice for all but very small inputs.

Az Sayıdaki Eleman İçin Big O
Az sayıdaki eleman için Big O'yu tartışmak anlamsızdır. Örneğin çok kısa bir mesafe, yürüyerek, bisikletle veya arabayla gidilebilir ve gereken süre belki de hepsi için o kadar az fark eder ki , O(1) ya da O(n) olmasının bir önemi kalmaz!

Big O'dan Söz Edilemeyen Durumlar
Sadece "Hello World" yazan bir programın, girdisi yani işlenen eleman sayısı olmadığı için Big O gösteriminden söz edilemez.

Big O notation exists to describe a relationship between the size of the input of a function and the number of operations that need to be performed to compute the result for that input.

Your operation has no input that the output can be related to, so using Big O notation is nonsensical. The time that the operation takes is independent of the inputs of the operation (which is...none). Since there is no relationship between the input and the number of operations performed, you can't use Big O to describe that non-existent relationship

Big O ve Diğer Gösterimler
Big O gösterimi yanında Teta ve Omega gösterimleri de var. Big O ve diğer gösterimler P (Polynomial) algoritmalar için kullanılır. Big O algoritmanın sadece üst sınırını belirtir yani upper bound'u belirtir.

Omega Gösterimi Nedir
Omega alt sınırı yani lower bound'u belirtir. Sembolü şöyledir. At nalı gibidir.

Ω(⋅) is a lower bound

Teta Gösterimi Nedir

Teta algoritmanın alt ve üst sınırını belirtir.

The Theta-notation asymptotically bounds a function from above and below. When we have only an asymptotic upper bound, we use O-notation.

Sembolü şöyledir. O harfinin ortasında yatay bir çizgi var gibidir.

Θ(1)

Asymptotically Optimal Nedir
Bir algoritma özel bir iş/durum için en iyi sonucu veriyorsa Asymptotically Optimal denir.

Big O Karşılaştırması
Aşağıda bazı algoritmaların karşılaştırmaları var.

Big O ve Veri Yapıları
Veri yapılarının Big O değerleri şöyle.

Big O ve Sabitler - Scalar (Sayıl) Value
Big O sabitleri dikkate almaz. Bu yüzden f(n) = n ve g(n) = 10n her zaman O(n) kabul edilirler.

Logaritma olsaydı da sabitler fark yaratmazdı. Matematiksel olarak aynı kabul ediliyorlar ve bu durum algoritmaları karşılaştırmayı kolaylaştırıyor.

Ancak pratik kullanımda an^2 + bn + c gibi bir formülde a, b ve c'nin önemsiz kabul edilmesi doğru olmayabilir. Çünkü 2n^2 ve n^2 şeklinde çalışan iki algoritma arasından n^2'yi tercih etmek gerekir. Yani pratikte sabitler önemli.

Big O ve Veri Yapıları Üzerindeki Farklı İşlemler
Veri yapısına ekleme, silme gibi işlemlerin genellikle maliyetleri farklı değerlerdir. Bu değerlerin en iyi, en kötü ve ortalama maliyetleri de vardır.

O(1) - Constant
O(1) - Constant yazısına taşıdım.

O(log(n)) - Logaritmic
O(log(n) - Logaritmic yazısına taşıdım

O (n) - Linear
O(n) - Linear yazısına taşıdım.

O (n log(k))
Burada k en büyük/küçük k tane elemanı temsil ediyor. Örneğin bir dizideki en büyük 100 elemanı bulmanın maliyeti bu olabilir. En büyük en küçük k tane eleman saklamak için priority queue kullanılır. O (n log(n)) algoritmalara göre maliyeti daha düşüktür.


O(n log(n)) - Quasi Linear
Quasi Linear ismi çok tuhaf.
log (n) n sayısının 2 tabanındaki logaritması anlamına geliyor. Yani n sayısının kaç defa 2'ye bölünebildiği demek. Genel olarak divide and conquer algoritmaları bu karmaşıklığa sahiptir.

Özel olaraksa Quicksort örnek verilebilir. 

Aşağıdaki kod parçasında dıştaki döngü O(n) içteki döngü ise j*=2 yüzünden O(log n). O(n) * O(log n) ise = O (n log(n))

int sum = 0;

for(i = 1; i <= inputSize; i++){
    for(j = i; j < inputSize; j *=2 ){
        printf("The value of sum is %d\n",++sum);
    }
}

O(n2) - İkinci Dereceden Yani Quadratic
O(n^2) - Quadratic yazısına taşıdım

O(n3) - Üçüncü Dereceden Yani Cubic
Matris çarpımı iç içe geçmiş üç döngü içerdiği için üçüncü derecedendir. Açıklamayı burada bulabilirsiniz.

O(n!)
Permütasyon hesaplamalarında bu değeri elde ediyoruz. O(n!) O(n^n)'den yine de daha iyidir. Recursive bir örnek için buraya bakabilirsiniz. Travelling Salesman (gidilmesi gereken noktaların hepsine sadece bir kez uğrayarak maliyeti en düşük şekilde tutarak başlangıca dönmeyi gerektiren problem) probleminin de permütasyon kullandığı için O(n!) olduğu yazılı.

Big O ve İç içe Döngüler
İç içe döngü kullanan aşağıdaki sorunun cevabı burada. Aşağıdaki sorunun cevabı 2n-1

Big O ve Auxilary Storage
Algoritmalar incelenirken sadece time complexity özelliklerine değil aynı zamanda ne kadar hafıza kullandıklarına da bakılabilir. Örneğin Sorting algoritm sayfasında Memory başlığı altında algoritmanın ne kadar hafızaya ihtiyaç duydukları da incelenmiş. 

Quicksort gibi bir algoritma özyinelemeli (recursive) olarak çalışıyorsa ,log(n) stack büyüklüğüne ihtiyaç duyar. Merge sort ise O(n) heap büyüklüğüne ihtiyaç duyabilir.

Algoritma Analizi

1. Algoritma ve Problem Arasındaki Fark Nedir

• Problem cevabını istediğimi sorudur.
• Algoritma problemin adım adım çözümüdür. 

Her algoritmanın time complexity değeri vardır. Problemler ise bir complexity kümesine dahildirler. P, NP PSPACE, EXPTIME complexity kümeleridir. Bu kümelere ait problemler bulunur, algoritmalar değil. P kümesine ait bir problemin - örneğin sıralama problemi - O(1) , O(n) gibi farklı time comlexity değerine sahip algoritmik çözümleri bulunabilir.

2. Complexity Theory
P (Polynomial) problemler bir formül ile çözülebilirler, NP (Non Polynomial) olanlar ise formül ile değil, sezgisel (heuristic) olarak çözülen problemlerdir. NP problemler formüle dökülemese bile verilen yanıtın doğrulanması konusunda çoğunluklar zorluk çıkarmazlar. Şöyle bir tablo herşeyi açıklıyor.

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

Bir problemin P Olması Neden Önemlidir?

P çok maliyetli olsa bile zaman içinde bir çok P probleme daha basit çözümler bulunmuştur. Problemin P olması ileride daha verimli olabileceği anlamına gelir.

NP
Açıklaması şöyle. NP problem illa çözmesi çok zor olan problem anlamına gelmez.

There are many NP problems which are easy to solve. "NP" simply means "easy to verify". It does not mean hard to solve.

What you are probably thinking of is NP-complete problems which is a subset of the NP problems for which we have very, very good evidence to think they are hard.

NP-Complete
NP-Complete yazısına taşıdım.

NP-Hard
NP-Hard yazısına taşıdım.

Big O Nedir?
Bir O Nedir yazısına taşıdım.

Algoritma Analizi - O (n) Linear

Giriş
Lineer grafik anlamına gelir.

ArrayList'e Eleman Ekleme
ArrayList'e yeni elemen ekleme veya çıkarma diğer tüm elemanların kaydırılmasını gerektirdiği için O(n)'dir.

Array'i Döndürme
Şöyle yaparız.

/* Function to left rotate arr[] of size n by d */
void leftRotate(int arr[], int d, int n)
{
  rvereseArray(arr, 0, d-1);
  rvereseArray(arr, d, n-1);
  rvereseArray(arr, 0, n-1);
}

/*Function to reverse arr[] from index start to end*/
void rvereseArray(int arr[], int start, int end)
{
  int temp;
  while (start < end)
  {
    temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    start++;
    end--;
  }
}

Array'i XOR'layarak Dolaşma
Soru şöyle

Consider an array of integers, where all but one of the integers occur in pairs. In other words, every element in occurs exactly twice except for one unique element.

Given the array find and print the unique element. [2,3,1,3,2] -> result is 1

Şöyle yaparız.

private static int lonelyInteger(int[] a) {
  int b = a[0];

  for(int i = 1; i < a.length; i++){
    b ^= a[i];
  }
  return b;       
}

Least Common Multipe - En Büyük Ortak Kat

Şöyle hesaplarız. Aslında bu O(1) 'dir. 

static BigInteger lcm(BigInteger a, BigInteger b) {
    return a.multiply(b).divide(a.gcd(b));
}

Ancak bir dizi için hesaplamak gerekiyorsa döngü kurmak gerekir çünkü formül şöyle

LCM(a, b, c) = LCM(LCM(a, b), c)

Greatest Common Divisor - En Büyük Ortak Bölen

Hata durumlarını ele almazsak en basit hali işe şöyledir. p çok büyük ve q çok küçük ise en kötü durumda (worst case) şaşırtıcı bir şekilde O(n)'dir.

gcd(p,q)
  if (p == q)
    return q
  if (p < q)
    gcd(q,p)
  while (q != 0)
    temp = p % q
    p = q
    q = temp
  return p

Aynı şeyi özyinelemeli olarak şöyle yaparız. Bu aynı zamanda GCD bulmak için "Euclid's Algorithm" olarak ta bilinir.

public static long gcd(long a, long b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

Döngülü çözümü C++ ile gerçekleştirmek için şöyle yaparız.

int gcd(int a, int b) const {
  int temp{};

  a = std::abs(a);
  b = std::abs(b);

  if (b > a) {
    temp = a;
    a = b;
    b = temp;
  }

  while(b != 0) {
    temp = b;
    b = a % b;
    a = temp;
  }

  return a;
}

RetainAll
Hash kullanan collection'lardaki retainAll(Collection) metodu (elde tut). Bu metod ile verilen collection'daki elemanlar hariç geri kalan herşey silinir. hash aramanın maliyeti O(1)'dir. İşlem verilen collection'daki her eleman için tekrarlanınca maliyeti O(n) olur.

Piramit
Piramit çıktısını yazdırmak için şöyle yaparız. En dıştaki döngü sayısı önemlidir. İçteki döngü sayısı n'e bağımlı olduğu için dikkate alınmaz.

for i from 1 to n
  for j from 1 to i
    print "$j "
  print "\n"

Çıktı olarak şunu alırız

1
1 2
1 2 3

Turnuva Eşleşmesi
Biraz piramite benziyor. Şöyle yaparız.

for(int i = 0; i < players.length-1; i+=2)
    System.out.println(players[i] + " - " + players[i+1]);
for(int i = 1; i < players.length-1; i+=2)
    System.out.println(players[i] + " - " + players[i+1]);

for(int dist = 2; dist < players.length; dist++)
for(int i = 0; i + dist < players.length; i++)
    System.out.println(players[i] + " - " + players[i+dist]);

Çıktı olarak şunu alırız

0 - 1, 2 - 3, 4 - 5, 
1 - 2, 3 - 4, 5 - 6, 
0 - 2, 1 - 3, 2 - 4, 3 - 5, 4 - 6, 
0 - 3, 1 - 4, 2 - 5, 3 - 6, 
0 - 4, 1 - 5, 2 - 6, 
0 - 5, 1 - 6, 
0 - 6, 

Remove Duplicates From Sorted Array - Two pointer technique
Algoritma şöyle. Piramit örneğinde olduğu gibi en dıştaki döngü önemlidir. Two pointer technique kullanır. i slow runner, j ise fast runner olarak adlandırılır. j tüm diziyi dolaştığı için O(n)'dir.

public int removeDuplicates(int[] nums) {

    if (nums.length == 0) return 0;

    int i = 0;

    for (int j = 1; j < nums.length; j++) {

        if (nums[j] != nums[i]) {

            i++;

            nums[i] = nums[j];

        }

    }

    return i + 1;

}

HasCycle - Two pointer technique
Şöyle yaparız. Slow teker teker ilerler. fast ise ikişer ikişer ilerler. Eğer fast slow'a yetişirse döngü vardır.

public boolean isCyclic(Node first) {
  if(first == null) {
    return false;
  }
  Node fast = first;
  Node slow = first;
  while(fast.getNext() != null && fast.getNext().getNext() != null) {
    slow = slow.getNext();
    fast = fast.getNext().getNext();
    if(slow == fast) {
      return true;
    }
  }
  return false;
}

Diğer seçenekleri de görmek adına hash set kullanarak O(n)'de çözmek için şöyle yaparız.

bool check_for_cycle_short(const Node *p)
{
  std::unordered_set<const Node*> mm;
  for (; p && mm.insert(p).second; p = p->next);
  return p != nullptr;
}

Diğer seçenekleri de görmek adına O(n^2) olarak çözmek için şöyle yaparız.

bool check_for_cycle_long(const Node *p)
{
  for (; p; p = p->next)
  {
    for (const Node *q = p->next; q; q = q->next)
    {
      if (q == p)
        return true;
      }
  }
  return false;
}

Determine if an array is the reverse of a second array

İlk diziyi soldan sağa, ikinci diziyi sağdan sola dolaşır her elemanı karşılaştırırız. Şöyle yaparız.

public boolean areReversed(int[] array1, int[] array2) {
  if (array1.length != array2.length) {
    return false;
  }
  int length = array1.length;
  for (int i = 0; i < length; i++) {
    if (array1[i] != array2[length - i - 1]) {
      return false;
    }
  }
  return true;
}

Diziyi Sağdan ve Soldan Başlayarak Dolaşma
Diziyi Sağdan ve Soldan Başlayarak Dolaşma yazısına taşıdım.

Diğer
Bazen O(n) gibi görünen ancak bir hata durumunda erkenden biten kodlar olabiliyor. 

Örnek

Elimizde şöyle bir kod olsun. Bu kod da sanırım O (n)

do {
  // some operation with time complexity O(N)
} while (errorMetric > 0.01) // if this is false, we've reached convergence

Örnek

Elimizde şöyle bir kod olsun

int foo(int x){
  if (x == 0) return x;
  if (x == 42) return foo(42);        
  if (x > 0) return foo(x-1);            
  return foo(x/2);
}

Açıklaması şöyle. Eğer 42 ile çağrılmayacağını varsayarsak, bu değerler arasında en büyüğünü seçmek gerekir. Yani O (n) olur

- Don't ever call it with x >= 42.

- O(1) if x==0

- O(x) if x>0

- O(ln(x)) if x < 0