پیچیدگی زمان (Time Complexity) در برنامه نویسی

معرفی علامت O بزرگ

به محاسبات ریاضی برای حل یک مساله طراحی الگوریتم و به بررسی کیفیت اجرای یک الگوریتم آنالیز الگوریتم میگیم.

به الگوریتم جستجوی خطی توجه کنید:

function search(m: int, array: int[]): int {

  for 0<= i < array.length
    if m = array[i]
      return i

  return -1;
}
        

در الگوریتم بالا اگه متغیر m داخل آرایه به طول n نباشه، n بار طول میکشه تا همه ی متغیر های داخل آرایه رو با m مقایسه کنه و اگه وسط آرایه باشه n/2 بار و اگه ابتدای آرایه باشه 1 بار پس برای پیدا کردن m داخل آرایه سه حالت وجود داره، زمانی که m داخل آرایه نباشه بدترین حالت (worst-case) اتفاق می افته، زمانی که m وسط آرایه باشه حالت میانگین (average-case) پیش میاد و زمانی که m ابتدای آرایه باشه با اولین مقایسه index خونه ای که m داخلش قرار داره رو پیدا می کنه و بر میگردونه که بهترین حالت (best-case) پیش اومده.

در بدترین حالت (worst-case) برای یک آرایه به طول n، متغیر m با اعضای آرایه n بار مقایسه میشه، طول آرایه با زمان اجرای الگوریتم رابطه ی مستقیم داره و الگوریتم با یک نرخ خطی در حال رشده به عبارتی n بار داره یک کار رو تکرار میکنه که میگیم مرتبه ی بزرگی الگوریتم برابر با n است.

مرتبه ی بزرگی هر الگوریتم بیانگر نرخ رشد الگوریتم با افزایش ورودی در طول زمان اجراست و بهش پیچیدگی زمان (time complexity) الگوریتم میگیم.

برای نشون دادن مرتبه ی بزرگی هر الگوریتم، دانشمندان علوم کامپیوتر از علامت O بزرگ استفاده میکنن و ابتدای Order of Magnitiude است؛ مرتبه ی بزرگی الگوریتم در مثالی که زده شد برابر با O(n) است.

فرض کنید 7 تا الگوریتم داریم که مرتبه ی بزرگیشون به ترتیب برابر با O(1)، O(logn)، O(n)، O(n^2)، O(n^3) و O(2^n) است؛ در زیر نمودار نرخ رشد هر کدوم اورده شده است:

همونطور که در نمودار مشخصه با افزایش اندازه ی n بجز O(1) که ثابته سایر نمودار ها رشد به خصوص خودشونو دارن و بیشترین نرخ رشد برای O(2^n) و کمترین نرخ رشد برای O(logn) است.

نحوه ی محاسبه ی پیچیدگی زمان

معمولا پیچیدگی زمان یک الگوریتم رو با بدست اوردن مرتبه ی بزرگی الگوریتم از روی حلقه ها یا روند اجرای متد های بازگشتی، حساب می کنیم؛ در مثال قبل گفتیم مرتبه ی بزرگی الگوریتم جستجوی خطی O(n) است، حلقه n بار تکرار میشه و در هر تکرار یک بار مقدار m رو با اعضای آرایه مقایسه می کنه.

در محاسبه ی مرتبه ی بزرگی الگوریتم ها، تمام کار های محاسباتی مثل، ضرب، تقسیم، جمع، تفریق مقایسه و ... رو ثابت در نظر میگیریم که با علامت c یا O(1) نمایش می دیم؛ و ثابت ها و اعداد در تخمین مرتبه ی بزرگی یک الگوریتم بی تاثیر هستن از این رو از نوشتنشون میتونیم صرف نظر کنیم؛ در مثال قسمت قبل مرتبه ی بزرگی الگوریتم در واقع O(c * n) بود که از c صرف نظر کردیم.

در زیر چندتا جمع ریاضی پرکاربرد اورده شده که یاد گرفتنشون برای تخمین مرتبه ی بزرگی الگوریتم ها بدرد میخوره.

1 + 2 + 3 + ... + (n - 2) + (n -1) = n * ( n - 1) / 2 = O(n^2)

1 + 2 + 3 + ... + (n - 1) + n = n * (n + 1) / 2 = O(n^2)

a^0 + a^1 + a^2 + ... + a^(n-1) + a^(n) = (a^(n+1) - 1) / (a - 1) = O(a^n)

2^0 + 2^1 + 2^2 + ... + 2^(n-1) + 2^(n) = 2^(n+1) - 1 = O(2^n)
        

مثال

میخوایم مرتبه ی بزرگی شبه کد زیر رو حساب کنیم.

for 1<= i <= n i++
  k := k * 2
        

محاسبه ی k همون c الگوریتم است و حلقه n بار تکرار میشه، پس:

T(n) = O(c * n) = O(n)

مثال

میخوایم مرتبه ی بزرگی دو حلقه ی تو در تو رو حساب کنیم.

for 1 <= i <=n i++
  for 1 <= j <=n j++
    k := k + 1
        

افزایش مقدار k همون c مساله است

حلقه ی اول n بار تکرار میشه و با هر بار تکرار حلقه ی دوم n بار تکرار میشه پس:

T(n) = cn + cn + ... + cn 
     = c * (n + n ... + n) 
     = c * n ^ 2
     = O(c * n ^ 2)
     = O(n ^ 2)
        

مثال

for 1 <= i <=n i++
  for 1 <= j <= i j++
    k := k + i + j
        

در مثال بالا دو تا حلقه ی تو در تو وجود داره، با هر بار تکرار حلقه ی اول، حلقه ی دوم از یک تا i تکرار میشه یعنی حلقه ی دوم ابتدا ۱ بار بعد ۲ بار بعد ۳ بار ... و زمانی که i برابر با n شد، n بار تکرار میشه پس:

T(n) = (c * 1) + (c * 2) + (c * 3) + ... + (c * n)
     = c * (1 + 2 + 3 + ... + n)
     = c * (n * (n + 1) / 2
     = O(n * (n + 1) / 2)
     = O(n ^ 2)
        

مثال

for 1<= i <= 10 i++
  for 1<= j <= n j++
    k := k * 8
        

در مثال بالا حلقه ی اول 10 بار تکرار میشه و در هر بار تکرار حلقه ی دوم n بار تکرار میشه پس:

T(n)= cn + cn + (۱۰ بار) + cn = O(10cn) = O(n)

مثال

for 1<= i <= 10 i++
  v := v + i

for 1<= m <= n m++
  for 1<= p <=20 p++
    k := k + i
        

در مثال بالا حلقه ی اول ۱۰ بار تکرار میشه و ثابت مساله محاسبه ی v است پس:

c * 10 = O(1)

در دو حلقه ی تو در تو پایین، حلقه ی بیرونی n بار تکرار میشه و در هر بار تکرار حلقه ی درونی 20 بار تکرار میشه پس:

T(n) = (c * 20) + (c * 20) + ... + (c * 20) //n بار
     = (c * 20 * n)
     = O(n)
        

پیچیدگی زمان مساله میشه:

T(n) = O(n) + O(1) = O(n)

مثال

در زیر سه تا حلقه ی تو در تو وجود داره.

for 1<= i <= n i++
  for 1<= j <= n j++
    for 1<= k <= n k++
      l := l * i + j + k
        

در مثال بالا حلقه ی اول n بار تکرار میشه و با هر بار تکرار حلقه ی اول، حلقه ی دوم n بار تکرار میشه و با هر بار تکرار حلقه ی دوم، حلقه داخلی سوم n بار تکرار میشه پس:

ابتدا جواب دو تا حلقه ی داخلی رو پیدا میکنیم و بعد با حلقه ی خارجی جواب نهایی رو بدست میاریم:

(c * n) + (c * n) + (c * n) + ... + (c * n) = c * (n^2)

جواب بالا با هر بار تکرار حلقه ی بیرونی یک بار تکرار میشه و حلقه ی بیرونی خودش n بار تکرار میشه.

T(n) = (c * (n ^ 2)) + (c * (n ^ 2)) + ... + (c * (n ^ 2)) 
     = c * ((n ^ 2) + (n ^ 2) + ... + (n ^ 2))
     = c * n * (n ^ 2)
     = c * n ^ 3
     = O(c * n ^ 3)
     = O(n ^ 3)
        

محاسبه ی پیچیدگی زمان بعضی از الگوریتم های معروف

میخوایم پیچیدگی زمان چندتا از الگوریتم های پر کاربرد رو تخمین بزنیم.

function search(int m, int[] array): int{
  low := 0;
  high := array.length - 1;

  while(low < high){
    mid := (low + high) / 2
    if m < array[mid]
       high := mid
    else if m > array[mid]
       low := mid + 1
    else 
       return mid

     return -low -1;
  }
}
          

static int search(int m, int[] array){
  int low =0;
  int high = array.length - 1;

  while (low <= high){
      int mid = (low + high) / 2;
      if (m < array[mid]){
          high = mid;
      }else if (m > array[mid]){
          low = mid + 1;
      }else return mid;
  }

  return -low - 1;
}
          

fun search(m: Int, array: IntArray): Int {
        var low = 0
        var high = array.size - 1

        while (low <= high) {
            val mid = (low + high) / 2
            if (m < array[mid]) {
                high = mid
            } else if (m > array[mid]) {
                low = mid + 1
            } else return mid
        }


        return -low - 1
    }
          

T(n) = T(n/2) + c 
     = T(n/2^2) + c + c 
     = T(n/2^3) + c + c + c 
     = T(n/2^k) + kc 
     = 1 + kc 
     = O(1 + logn) 
     = O(logn)
          

function moveDisks(n: int){
  moveDisks(n, 'A', 'B', 'C')
}

function moveDisks(n: int, fromTower: char, toTower: char, auxTower: char){
  if n = 1
    print("Move disk " + n + " from " + fromTower + " to " + toTower)
  else
    moveDisks(n - 1, fromTower, auxTower, toTower)
    print("Move disk " + n + " from " + fromTower + " to " + toTower)
    moveDisks(n - 1, auxTower, toTower, fromTower)

}
          

static void moveDisks(int n){
  moveDisks(n, 'A', 'B', 'C');
}

static void moveDisks(int n, char fromTower, char toTower, char auxTower){
  if(n == 1){
    System.out.println("Move disk " + n + " from " + fromTower + " to " + toTower);
  }else{

    moveDisks(n - 1, fromTower, auxTower, toTower);

    System.out.println("Move disk " + n + " from " + fromTower + " to " + toTower);

    moveDisks(n - 1, auxTower, toTower, fromTower);

  }
}
          

fun moveDisks(n: Int){
  moveDisks(n, 'A', 'B', 'C')
}

fun moveDisks(n: Int, fromTower: Char, toTower: Char, auxTower: Char){
  if(n == 1){
    // Move last disk from A to B
    println("Move disk " + n + " from " + fromTower + " to " + toTower)
  }else{

    moveDisks(n - 1, fromTower, auxTower, toTower)

    println("Move disk " + n + " from " + fromTower + " to " + toTower)

    moveDisks(n - 1, auxTower, toTower, fromTower)

  }
}
          

T(n) = T(n - 1) + 1 + T(n - 1)
     = 2 * T(n - 1) + 1
     = 2 * (2 * T(n - 2) + 1) + 1
     = 2 * (2 * (2 * (T(n - 3) + 1)  + 1) + 1) + 1
     = 2 ^ (n - 1) * T(1) + 2 ^ (n - 2) + ... + (2 ^ 2) + (2 ^ 1) + 1
     = 2 ^ (n - 1) + 2 ^ (n - 2) + ... + 2 ^ 2 + 2 ^ 1 + 1
     = O(2 ^ n) + 1
          

function fib(index: long): long {
  if index = 0
    return 0
  if index = 1 or index = 2 
    return 1
  else 
    return fib(index - 1) + fib(index - 2)
}
          

static long fib(long index){
  if(index == 0)
    return 0
  else if(index == 1 || index == 2) 
    return 1;
  else 
    return fib(index - 1) + fib(index - 2);
}
          

fun fib(index: Long): Long{
  if(index == 0)
    return 0
  if(index == 1 or index == 2) 
    return 1
  else 
    return fib(index - 1) + fib(index - 2)
}
          

T(n) = T(n - 1) + T(n - 2) + c
     <= 2 * T(n - 1) + c
     <= 2 * (2 * T(n - 2) + c) + c
       ...
     = (2 ^ n) + nc
     = O(2 ^ n + nc)
     = O(2 ^ n)
          

function fib(n: long){
  f0 := 0
  f1 := 1
  f2 := 1 

  for 3<= i <=n i++
    f0 := f1
    f1 := f2
    f2 := f0 + f1

  return f2
}
          

static long fib(long n){
  long f0 = 0;
  long f1 = 1;
  long f2 = 1;

  for (int i= 3; i <= n; i++){
      f0 = f1;
      f1 = f2;
      f2 = (f1 + f0);
  }

  return f2;
}
          

fun fib(n: Long): Long {
    var f0: Long = 0
    var f1: Long = 1
    var f2: Long = 1

    for (i in 3..n) {
      f0 = f1
      f1 = f2
      f2 = (f1 + f0)
    }

    return f2
} 
          

خلاصه

• مرتبه ی بزرگی الگوریتم نرخ رشد الگوریتم در طول زمان است.
• مرتبه ی بزرگی یک الگوریتم بیان گر نرخ رشد الگوریتم با افزایش ورودی در طی زمان اجرای الگوریتم است.
• مرتبه ی بزرگی الگوریتم رو با علامت O بزرگ نشون می دیم.
• معمولا سه حالت رو برای یک الگوریتم در نظر میگیریم، بهترین حالت (best-case)، حالت میانگین (average-case) و بدترین حالت (worst-case).
• معمولا مرتبه ی بزرگی هر الگوریتم رو از روی بدترین حالت (worst-case) الگوریتم محاسبه می کنیم.