مصطلح ال Big O notation فى علوم الحاسوب

فى علوم الحاسوب نستخدم مصطلح ال Big O notation للتعبير عن كفائه او تعقيد خوارزميه فهذا المصطلح يستخدم للدلاله على اسوء سيناريو ممكن الحدوث وأيضا تستخدم لتوصيف الوقت والحجم الذي سياخذهما الكود عند وقت التشغيل.

O(1)

تستخدم للدلاله على ان الكود سياخذ نفس الوقت او المساحه حتى باختلاف المدخلات الى الكود مثال

def f(n):
    return 5

ففى حاله كانت n=1 سياخذ الكود نفس الوقت اذا كانت n=999999 فالكود لا يعتمد على المدخل .

O(N)

تستخدم للدلاله على ان زمن تنفيذ الكود يتناسب طرديا مع حجم المدخلات مثال

def search(alist, word):                 
    for element in alist:
        if element == word: return Found
    return NotFound

زمن هذا الكود يعتمد على على حجم المدخل المتمثل فى القائمه التى تحتوى على الكلمات والكلمه فبطول هذه القائمه يزيد على المرات التى يتم تفعيل ال loop فيها الى ان يتم ايجاد الكلمه , مصطلح ال Big O notation يصف دائما اسوء حاله وفى هذا المثال اسوء حاله هى عدم وجود الكلمه فى القائمه وبالتالى سيضطر البرنامج الى تنفيذ عدد مرات من ال loop بمقدار طول هذه القائمه فاذا كان طوله 15 كلمه سيتم تنفيذ ال loop خمسه عشر مره .

O(N2)

تستخدم للداله على ان زمن تنفيذ الكود ستناسب طرديا مع مربع حجم المدخلات مثال

def all_combinations(the_list):
   results = []
   for item in the_list:
       for inner_item in the_list:
           results.append((item, inner_item))
   return results

فى هذا الكود يعتمد الزمن الكلى له على مربع حجم المدخلات وذلك بسسب وجود مدارين فلكل مدخل موجود فى القائمه يتم عمل Loop فاذا كان هناك عدد N مدخلات فى القائمه فسيكون هناك عدد N*N = N2 مره لل Loop , فلو كانت القائمه تحتوى على [1,2,3] النتاج سيكون [ (3,3) , (3,2) , (3,1) , (2,3) , (2,2) , (2,1) , (1,3) , (1,22) , (1,11) ] .

O(2N)

تدل على ان زمن الداله يتضاعف مع كل اضافه كل مدخل فالداله الاسيه يزداد الزمن بطريقه اسيه مع كل مدخل مما يجعلها داله سيئه جدا

def fibonacci(n):
    if n == 1:
        return 1
    return n * fibonacci(n-1)

عليك تجنب هذه الدوال قدر المستطاع لان اداءها ضعيف جدا وتاخذ زمن كبير جدا

O(log N)

تعتبر اكثرهم خداعا لذلك ساحاول تبسيط الشرح قدر المستطاع , احد امثله هذه الداله هو البحث الثنائى او ما يعرف ب Binary search ففى البحث الثنائى يتم اختيار العنصر الذى يقع فى منتصف ال List ونقوم بمقارنته بالعنصر الذى نريد

البحث عنه فاذا كان هو تتم الداله بالنجاح واذا كان اصغر من العنصر الذى نبحث عنه نقوم بتطبيق نفس الداله Binary search ولكن على النصف الاصغر من ال List (العناصر التىتقع على يسار العنصر ) واذا كان العكس يتم تطبيق الداله على

النصف الاكبر من ال List (العناصر على يمين العنصر) الى ان يتم ايجاد العنصر . مما سبق نستنتج انه فى كل محاوله يقل عدد العناصر الى النصف فمثلا اذا تم تطبيق الداله على 10 عناصر فانها ستاخذ 1 ثانيه واذا تم تطبيقها على 100 عنصر

فانها ستاخد 2 ثانيه واذا تم تطبيقها على 1000 عنصر فانها ستاخذ 3 ثوان , يتضح ان بمضاعفه عدد المدخلات فان الزمن الذى ياخذ تنفيذ الكود يزداد بشكل بسيط جدا مما يجعل O(log N) نوع ذو كفائه واداء عالى جدا ويحبذ استخدامها عند

المدخلات الضخمه .

كان هذا شرح بسيط ل Big O notation التى تستخدم فى تحليل الاكواد لمعرفه كفائتها والسلام عليكم ورحمه الله .