راهنمای سریع نمادگذاری Big O برای محاسبه پیچیدگی محاسباتی

پیچیدگی زمانی چیست؟

پیچیدگی زمانی، اندازه گیری زمان لازم برای اجرای یک برنامه توسط کامپیوتر، به عنوان تابعی از طول ورودی است. اگرچه زمان یک فاکتور مهم هنگام نوشتن یک الگوریتم است، پیچیدگی زمانی در واقع با تعداد میلی ثانیه، ثانیه یا (خدای نکرده) دقیقه ای که طول می کشد تا برنامه کامل شود، اندازه گیری نمی شود. این به این دلیل است که مدت زمان لازم برای اجرای یک برنامه توسط رایانه اغلب به خودِ رایانه بستگی دارد. اجرای برنامه‌ای که در یک کامپیوتر 0.01 ثانیه طول می‌کشد، ممکن است در رایانه دیگر 0.08 ثانیه طول بکشد. این تفاوت، ناچیز به نظر می رسد، به خصوص با توجه به اینکه هر دو رایانه برنامه را با سرعت نسبتاً بالایی اجرا می کردند، اما این ناهماهنگی، به اندازه کافی قابل توجه است که این گونه اندازه گیری پیچیدگی (بر حسب زمان اجرا) مناسب برای سنجش کارایی یک الگوریتم نیست. به همین دلیل است که پیچیدگی زمانی با تعداد عملیات O که توسط الگوریتم، بر روی تعدادی عنصر n انجام می‌شود، اندازه‌گیری می‌شود، نه با مقدار زمانی که برای اجرا لازم است!

زمان ثابت - Constant Time — O(1)

زمان ثابت نشان می دهد که بدون توجه به طول ورودی، تعداد عملیات همیشه ثابت باقی می ماند.

const array1 = [6, 1, 5, 5, 4, 3]
const array2 = [4, 1, 99, 7, 3, 4, 1, 20, 5, 9, 200, 90]
function findThirdElement(array){
    return array[2]
}
console.log('Third element: ', findThirdElement(array1))
//=> Third element: 5
console.log('Third element: ', findThirdElement(array2))
//=> Third element: 99       

در این مثال، تابع findThirdElement()آرایه را دریافت کرده و سومین عنصر را برمی گرداند (عنصر در جیاگاه شاخص 2). پیچیدگی زمانی این تابع برابر O(1) است. زیرا تعداد عملیاتی که رخ می دهد مستقل از طول ورودی است. مهم نیست که array1 چقدر طولانی باشد، تابع همیشه عنصر سوم را پیدا کرده و برمی گرداند.

پیچیدگی O(1) به دلیل استقلال آن نسبت به طول ورودی، اندازه گیری ایده آلی برای پیچیدگی زمانی است.

زمان خطی-Linear Time — O(n)

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

const array = [0, 1, 2, 3, 4]

function hasMatch(array, num){
    for (let i = 0; i < array.length; i++){
        if (array[i] === num){
            return true
        }
    }
    return false
}

console.log('Has a Match?: ', hasMatch(array, 3))

//=> Has a Match?: true

console.log('Has a Match?: ', hasMatch(array, 5))

//=> Has a Match?: false

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

نماد O(n) یک اندازه گیری ایده آل برای پیچیدگی زمانی است زیرا تعداد عملیات با طول ورودی نسبت مستقیم دارد.

زمان مربعی Quadratic Time — O(n²)

زمان درجه دوم (مربعی) نشان می دهد که تعداد عملیات متناسب با مجذور طول ورودی است.

const array1 = [0, 4, 1, 2, 5]
const array2 = [3, 4, 2, 7]
const array3 = [7, 6, 8, 3]
function containsDuplicate(array1, array2){
    for (let i = 0; i < array1.length; i++){
        for (let j = 0; j < array2.length; j++){
            if (array1[i] === arrray2[j]){
                return true
            }
        }
    }
    return false
}
console.log('Contains Duplicate?: ', containsDuplicate(array1, array2))
//=> Contains Duplicate?: true
console.log('Contains Duplicate?: ', containsDuplicate(array1, array3))
//=> Contains Duplicate?: false

در تابع بالا، containDuplicate()، دو آرایه وارد شده و با یکدیگر مقایسه می شوند. این تابع در هر دو آرایه در یک حلقه تودرتو حلقه می زند و هر عنصر در آرایه اول را با هر عنصر در آرایه دوم مقایسه می کند تا زمانی که یک عنصر تکراری پیدا کند. پیچیدگی زمانی این تابع O(n²) است زیرا حاوی یک حلقه تو در تو است که هر حلقه به ترتیب به طول آرایه 1 و آرایه 2 بستگی دارد.

نماد O(n²) یک اندازه گیری ایده آل برای پیچیدگی زمانی نیست زیرا تعداد عملیات به صورت تصاعدی با افزایش ورودی افزایش می یابد.

زمان نمایی Exponential Time — O(2^n)

زمان نمایی نشان می دهد که تعداد عملیات متناسب با دو با توان n است که n طول ورودی است.

function fibonacci(num){
    if (num <= 1){
        return num
    }else{
        return fibonacci(num - 2) + fibonacci(num - 1)
    }
}
console.log('Fibonacci: ', fibonacci(4))
//=> Fibonacci: 3
console.log('Fibonacci: ', fibonacci(10))
//=> Fibonacci: 55
console.log('Fibonacci: ', fibonacci(20))
//=> Fibonacci: 6765

تابع fibonacci()یک عدد یا یک شاخص در دنباله فیبوناچی می گیرد و مقدار دنباله فیبوناچی را در آن شاخص محاسبه کرده و برمی گرداند. این یک تابع بازگشتی است، به این معنی که حداقل یک بار خود را فراخوانی می کند.

پیچیدگی زمانی تابع O(2^n) است. این در مقیاس کوچک مشکلی ندارد اما با افزایش ورودی به سرعت از کنترل خارج می شود و برای نوشتن الگوریتم ها پیچیدگی زمانی ندارد.

زمان فاکتوریل-Factorial Time — O(n!)

زمان فاکتوریل نشان می دهد که تعداد عملیات متناسب با n فاکتوریل است.

const array1 = ['a', 'b', 'c', 'd', 'e', 'f']
const array2 = ['dog', 'cat', 'ferret']

function possibleCombinations(array){
    let total = array.length
    for (let i = 1; i < array.length; i++){
        total = (total * (array.length - i))
    }
    return total
}
console.log('The total number of possible combinations is: ', possibleCombinations(array1))
//=> The total number of possible combinations is: 720
console.log('The total number of possible combinations is: ', possibleCombinations(array2))
//=> The total number of possible combinations is: 6

تابع، () possibleCombinations، یک آرایه را می گیرد و تعداد کل ترکیبات ممکن بین همه عناصر را برمی گرداند. فاکتوریل یک تابع ریاضی است که در آن عدد n در هر عدد صحیح بین 1 و n-1 ضرب می شود. مثلا 5! به صورت 5x4x3x2x1 = 120 ارزیابی می شود. همانطور که در بالا ذکر شد، تفاوت بین 3! و 6! بسیار زیاد است، به همین دلیل است که این بدترین عمل مطلق در نوشتن الگوریتم ها در نظر گرفته می شود زیرا تعداد عملیات !n افزایش می یابد. هر بار که ورودی افزایش می یابد. تقریباً هرگز موردی وجود ندارد که در آن O(n!) استفاده شود، اما دانستن هر دو روش مهم است.

منبع

https://medium.com/weekly-webtips/a-quick-guide-on-big-o-notation-time-complexity-2ada6ce6c546