من الأمثلة على الخوارزميات التي O(1) ، O(n log n) و O(log n) تعقيدات

Question

ما هي بعض الخوارزميات التي نستخدمها يوميا وقد O(1) ، O(n log n) و O(log n) تعقيدات?

Answer 1

إذا كنت تريد أمثلة من الخوارزميات/مجموعة من البيانات مع مرور الوقت التعقيد على النحو الوارد في السؤال هنا هو قائمة صغيرة -

O(1) الوقت

• الوصول إلى مؤشر مجموعة (int a = ARR[5];)
• إدراج عقدة في قائمة مرتبطة
• دفع نصيف على المكدس
• الإدراج وإزالة من الانتظار
• العثور على الوالدين أو يسار/يمين الطفل عقدة في شجرة المخزنة في صفيف
• القفز إلى التالي/السابق عنصر في قائمة مرتبطة مضاعف

O(n) الوقت

باختصار, كل القوة الغاشمة الخوارزميات ، أو مستجد تلك التي تتطلب الخطي ، على أساس O(n) تعقيد الوقت

• تعبر مجموعة
• تعبر قائمة مرتبطة
• البحث الخطي
• حذف عنصر معين في قائمة مرتبطة (غير مصنفة)
• مقارنة سلسلتين
• التحقق من سياق متناظر
• عد/دلو نوع وهنا أيضا يمكنك أن تجد أكثر من مليون مثل هذه الأمثلة....

---

O(log n) الوقت

• البحث الثنائية
• العثور على أكبر/أصغر عدد في شجرة البحث الثنائية
• بعض فرق تسد الخوارزميات على أساس خطي وظائف
• حساب أرقام فيبوناتشي - أفضل طريقة الفرضية الأساسية هنا هي عدم استخدام البيانات كاملة ، والحد من مشكلة الحجم مع كل التكرار

---

O(n log n) الوقت

عامل 'log n' هو عرض من خلال جلب بعين الاعتبار فرق تسد.بعض من هذه الخوارزميات هي أفضل الأمثل منها و استخدامها في كثير من الأحيان.

• دمج النوع
• الكومة
• نوع سريع
• بعض فرق تسد خوارزميات تقوم على تحسين O(n^2) الخوارزميات

---

O(n^2) الوقت

هذه هي تلك التي من المفترض أن تكون أقل كفاءة الخوارزميات إذا كان س(nlogn) نظيراتها الحاضر.التطبيق العام قد تكون القوة الغاشمة هنا.

• فقاعة نوع
• نوع الإدراج
• اختيار نوع
• تعبر بسيطة 2D array

Answer 2

مثال بسيط على O(1) قد يكون return 23; - مهما كانت المدخلات ، سيعود هذا في وقت ثابت ومحدود.

مثال نموذجي على O(N log N) سيتم فرز صفيف الإدخال مع خوارزمية جيدة (مثل دمج).

مثال نموذجي إذا O(log N) سوف يبحث عن قيمة في صفيف الإدخال المصنفة عن طريق التشريح.

Answer 3

o (1) - معظم إجراءات الطهي هي o (1) ، أي أن الأمر يستغرق وقتًا مستمرًا حتى لو كان هناك عدد أكبر وتحتاج إلى تقسيم الطبخ)

o (logn) - العثور على شيء في دفتر الهاتف الخاص بك. فكر في البحث الثنائي.

o (n) - قراءة كتاب ، حيث n هو عدد الصفحات. إنه الحد الأدنى من الوقت الذي يستغرقه قراءة كتاب.

o (nlogn) - لا أستطيع التفكير على الفور في شيء يمكن للمرء أن يفعله كل يوم هو nlogn ... إلا إذا قمت بفرز البطاقات عن طريق الاندماج أو النوع السريع!

Answer 4

يمكنني أن أقدم لك بعض الخوارزميات العامة ...

• o (1): الوصول إلى عنصر في صفيف (أي int i = a [9])
• o (n log n): Quick أو Mergesort (في المتوسط)
• س (سجل ن): البحث الثنائي

ستكون هذه هي ردود الأمعاء لأن هذا يبدو وكأنه واجب منزلي/مقابلة نوع من الأسئلة. إذا كنت تبحث عن شيء أكثر واقعية ، فسيكون الأمر أصعب قليلاً لأن الجمهور بشكل عام لن يكون لديه أي فكرة عن التنفيذ الأساسي (تجنيب المصدر المفتوح بالطبع) للتطبيق الشهير ، كما أن المفهوم بشكل عام ينطبق على "تطبيق"

Answer 5

لم يتم قياس تعقيد تطبيق البرنامج ولا يتم كتابته بالتدوين الكبير. من المفيد قياس تعقيد الخوارزمية ومقارنة الخوارزميات في نفس المجال. على الأرجح ، عندما نقول يا (ن) ، نعني أنه "o (n) مقارنات"أو" O (N) العمليات الحسابية ". وهذا يعني ، لا يمكنك مقارنة أي زوج من الخوارزميات أو التطبيقات.

Answer 6

س (1): العثور على أفضل خطوة تالية في الشطرنج (أو اذهب لهذه المسألة). نظرًا لأن عدد حالات اللعبة محدود ، فهو فقط O (1) :-)

Answer 7

o (1) - حذف عنصر من قائمة مرتبطة بشكل مضاعف. على سبيل المثال

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    int data;
} node;


void delete(node **head, node *to_delete)
{
    .
    .
    .
}

Answer 8

يمكنك إضافة الخوارزميات التالية إلى قائمتك:

O(1) - تحديد ما إذا كان الرقم متساويًا أو غريبًا ؛ العمل مع هاشماب

O(logN) - الحوسبة x^n ،

O(N Log N) - أطول بعد زيادة بعد

Answer 9

يشتهر O (n log n) المقيمة العلوية على مدى السرعة التي يمكنك بها فرز مجموعة تعسفية (على افتراض نموذج حوسبة قياسي وليس متوازيًا).

Answer 10

0 (logn)-البحث الثنائي ، عنصر الذروة في صفيف (يمكن أن يكون هناك أكثر من ذروة واحدة) 0 (1)-في بيثون يحسب طول القائمة أو السلسلة. تستغرق وظيفة LEN () 0 (1) الوقت. يستغرق الوصول إلى عنصر في صفيف 0 (1) وقت. اضغط التشغيل في مكدس يستغرق 0 (1) الوقت. 0 (nlogn) -kerge sort. الفرز في Python يستغرق وقت nlogn. لذلك عندما تستخدم listname.sort () يستغرق وقت nlogn.

يستغرق البحث في جدول التجزئة في بعض الأحيان أكثر من وقت ثابت بسبب الاصطدامات.

Answer 11

س (2^ن)

س (2^ن) يدل على خوارزمية يتضاعف نموها مع كل إضافة إلى مجموعة بيانات الإدخال. منحنى نمو O (2^ن) الوظيفة أسية - تبدأ ضحلة للغاية ، ثم الارتفاع في النزول. مثال على O (2^ن) الوظيفة هي الحساب العودية لأرقام فيبوناتشي:

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}