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