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.