بیگ اُ (big O) چیست؟ و انواع آن

به نام خدا

هر زمانی حرف از الگوریتم و پرفومنس (performance) شود، نمی توان از Big O حرف نزد.

Big O چیست؟

Big O روشی برای سنجش کارایی انجام یک الگوریتم است. هر چه Big O بیشتر باشد، کارایی الگوریتم مورد نظر، کمتر است.

برای بررسی الگوریتم ها، چند نوع کلی Big O داریم که در ادامه به معرفی هر یک از آنها خواهم پرداخت. در Big O، فقط شیب نمودار مهم است. برای محاسبه Big O، بدترین حالت ممکن را در نظر می گیریم. یعنی تصور می کنیم کاری که می خواهیم انجام دهیم، در آخرین تلاش انجام شده. به عنوان مثال، الگوریتم جست و جو را در نظر بگیرید. Big O را با این تصور محاسبه می کنیم که آخرین تلاش ما، منجر به یافتن می شود.

Constant

در این نوع Big O،‌ تعداد ورودی مهم نیست و همیشه پرفورمنس، ثابت می ماند. بیگ اُ Constant را به صورت (O(1 نشان می دهند.

مثال:

def return_third(the_list):
  return the_list[2]

در این مثال،‌ تعداد اعضای the_list، هیچ تاثیری در کارایی الگوریتم ندارند. بهترین نوع Big O همین است. زیرا همواره در بهترین حالت ممکن است.

Linear

این نوع بیگ اُ که به صورت (O(n نمایش داده می شود، نشان میدهد که کارایی الگوریتم ما، به صورت خطی است. یعنی هرچه ورودی این الگوریتم بیشتر باشد،‌ به همان نسبت، کارایی پایین میاید.

مثال:

def print_items(the_list):
  for item in the_list:
    print(items)

در مثال بالا، هر چه عضو the_list بیشتر شود، Big O هم به همان نسبت بیشتر میشود.

Quadratic

این نوع از Big O، بسیار بدتر و خطرناک تر از Linear است. آن را با (O(n^2 نمایش میدهند. نمودار آن بخشی از سهمی است و با بیشتر شدن ورودی،‌ n برابر افزایش میابد.

مثال:

def print_items_pro(the_list):
  for item in the_list:
    for members in the_list:
        print(item, member)

در مثال بالا، به ازای هر عضو لیست، دو با لیست را پیشمایش کردیم.

Exponential

این نوع Big O،‌ یکی از بدترین کارایی ها را داراست. حتی بدتر از Quadratic. آن را با (O(2^n نمایش می دهند. نمودار این نوع نیز، به صورت نمایی است ولی با شیب بسیار زیاد.

مثال:

def fibo(num):
  if num == 1:
    return 0
  elif num == 2:
    return 1
  return fibo(num-1)+fibo(num-2)

در این الگوریتم، بار ها و بار ها پیمایش اتفاق میافتد. در نتیجه کارایی آن پایین میاید. برای اطلاعات بیشتر درباره الگوریتم بالا و جایگزین آن، می توانید این پست را بخوانید.

Logarithmic

بالاخره به نوعی از Big O رسیدیم که نشان دهنده خوب و کارا بودن الگوریتم ما است. این نوع بیگ اُ را بصورت (O(log n نشان می دهند. شیب آن کم است و هر چه ورودی بیشتر می شود، شیب باز هم کمتر می شود.

مثال:

جست و جوی دوتایی (Binary) نمونه ای از این نوع الگوریتم است.

def binarySearch (arr, l, r, x):
    if r >= l:
        mid = l + (r - l)
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
        else:
            return binarySearch(arr, mid + 1, r, x)

نحوه انجام و اجرای مثال بالا:

با تشکر از همراهی شما. لطفا نظرات خود را کامنت کنید تا مقالات بهتری تقدیم حضورتان کنم.