ماذا يعني o (log n) بالضبط؟

Question

أنا أتعلم عن أوقات تشغيل تدوين كبيرة وأوقات مبهجة. أنا أفهم فكرة على) الوقت الخطي ، مما يعني أن حجم المدخلات يؤثر على نمو الخوارزمية بشكل متناسب ... والشيء نفسه ينطبق ، على سبيل المثال ، الزمن التربيعي على²) الخ .. حتى الخوارزميات ، مثل مولدات التقليب ، مع على!) مرات ، التي تنمو من قبل العوامل.

على سبيل المثال ، الوظيفة التالية هي على) لأن الخوارزمية تنمو بما يتناسب مع مدخلاتها ن:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

وبالمثل ، إذا كانت هناك حلقة متداخلة ، فسيكون الوقت o (n²).

لكن ما هو بالضبط س (سجل ن)؟ على سبيل المثال ، ماذا يعني القول أن ارتفاع شجرة ثنائية كاملة س (سجل ن)?

أنا أعرف (ربما ليس بتفصيل كبير) ما هي اللوغاريتم ، بمعنى أن: سجل₁₀ 100 = 2 ، لكنني لا أستطيع أن أفهم كيفية تحديد وظيفة مع وقت لوغاريتمي.

Answer 1

لا أستطيع أن أفهم كيفية تحديد وظيفة مع وقت السجل.

أكثر السمات شيوعًا لوظيفة وقت التشغيل اللوغاريتمي هي:

• يعد اختيار العنصر التالي الذي يؤدي فيه بعض الإجراءات أحد الاحتمالات العديدة ، و
• سيحتاج واحد فقط إلى اختياره.

أو

• العناصر التي يتم تنفيذ الإجراء هي أرقام N

هذا هو السبب ، على سبيل المثال ، البحث عن الأشخاص في دفتر الهاتف هو O (log n). لا تحتاج إلى التحقق كل الشخص في دفتر الهاتف للعثور على الصحيح ؛ بدلاً من ذلك ، يمكنك ببساطة التقسيم والخروج من خلال البحث بناءً على المكان الذي يكون فيه اسمه أبجديًا ، وفي كل قسم ، تحتاج فقط إلى استكشاف مجموعة فرعية من كل قسم قبل أن تجد في النهاية رقم هاتف شخص ما.

بالطبع ، سيظل دفتر هاتف أكبر يستغرق وقتًا أطول ، لكنه لن ينمو بالسرعة التي تزيد بها الزيادة النسبية في الحجم الإضافي.

---

يمكننا توسيع مثال دفتر الهاتف لمقارنة أنواع العمليات الأخرى و هُم وقت الركض. سوف نفترض أن دفتر هاتفنا لديه الأعمال ("الصفحات الصفراء") التي لها أسماء فريدة و اشخاص ("الصفحات البيضاء") التي قد لا تحتوي على أسماء فريدة. يتم تعيين رقم هاتف لشخص واحد أو عمل واحد. سوف نفترض أيضًا أن الأمر يستغرق وقتًا مستمرًا للوجه إلى صفحة معينة.

فيما يلي أوقات التشغيل لبعض العمليات التي قد نؤديها على دفتر الهاتف ، من الأفضل إلى الأسوأ:

• س (1) (أفضل حالة): بالنظر إلى الصفحة التي يوجد فيها اسم الشركة واسم العمل ، ابحث عن رقم الهاتف.

• س (1) (الحالة المتوسطة): بالنظر إلى الصفحة التي يوجد فيها اسم الشخص واسمه ، ابحث عن رقم الهاتف.

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

• على): ابحث عن جميع الأشخاص الذين تحتوي أرقام هواتفهم على الرقم "5".

• على): بالنظر إلى رقم الهاتف ، ابحث عن الشخص أو العمل بهذا الرقم.

• o (n log n): كان هناك مزيج في مكتب الطابعة ، وكان دفتر هاتفنا قد تم إدخال جميع صفحاته بترتيب عشوائي. قم بإصلاح الطلب بحيث يكون صحيحًا من خلال النظر إلى الاسم الأول في كل صفحة ثم وضع تلك الصفحة في المكان المناسب في دفتر هاتف جديد فارغ.

بالنسبة للأمثلة أدناه ، نحن الآن في مكتب الطابعة. تنتظر كتب الهاتف أن يتم إرسالها بالبريد إلى كل مقيم أو عمل تجاري ، وهناك ملصق على كل دفتر هاتفي يحدد أين يجب إرساله بالبريد إليه. كل شخص أو عمل يحصل على دفتر هاتف واحد.

• o (n log n): نريد تخصيص دفتر الهاتف ، لذلك سنجد كل شخص أو اسم عمل في نسخته المحددة ، ثم قم بتعليق اسمه في الكتاب واكتب ملاحظة شكر قصيرة على رعايتهم.

• على²): حدث خطأ في المكتب ، ولكل إدخال في كل من كتب الهاتف "0" في نهاية رقم الهاتف. خذ بعض البيض وإزالة كل صفر.

• س (ن · ن!): نحن على استعداد لتحميل كتب الهاتف على رصيف الشحن. لسوء الحظ ، فإن الروبوت الذي كان من المفترض أن يحمل الكتب قد ذهب إلى haywire: إنه يضع الكتب على الشاحنة بترتيب عشوائي! والأسوأ من ذلك أنه يقوم بتحميل جميع الكتب على الشاحنة ، ثم يتحقق لمعرفة ما إذا كانت في الترتيب الصحيح ، وإذا لم يكن الأمر كذلك ، فإنه يفرغها ويبدأ من جديد. (هذا هو اللعين فرز بوغو.)

• على^ن): يمكنك إصلاح الروبوت بحيث يقوم بتحميل الأشياء بشكل صحيح. في اليوم التالي ، يلعب أحد زملائك في العمل مزحة عليك وأسلاك روبوت قفص الاتهام إلى أنظمة الطباعة الآلية. في كل مرة يذهب الروبوت لتحميل كتاب أصلي ، تقوم طابعة المصنع بتشغيل مكرر لجميع كتب الهاتف! لحسن الحظ ، فإن أنظمة كشف الأخطاء الروبوت متطورة بدرجة كافية بحيث لا يحاول الروبوت طباعة المزيد من النسخ عندما يواجه كتابًا مكررًا للتحميل ، ولكن لا يزال يتعين عليه تحميل كل كتاب أصلي ومكرر تم طباعته.

لمزيد من التفسير الرياضي ، يمكنك الخروج من كيفية وصول التعقيد الزمني إليه log n هنا. https://hackernoon.com/what-does-tim-complexity-o-log-n-actally-mean-45f94bb5bfbf

Answer 2

تم بالفعل نشر العديد من الإجابات الجيدة على هذا السؤال ، لكنني أعتقد أننا نفتقد حقًا الإجابة المهمة - أي الإجابة المصورة.

ماذا يعني القول أن ارتفاع شجرة ثنائية كاملة هو o (log n)؟

الرسم التالي يصور شجرة ثنائية. لاحظ كيف يحتوي كل مستوى على ضعف عدد العقد مقارنة بالمستوى أعلاه (وبالتالي الثنائية):

البحث الثنائي مثال على التعقيد O(log n). دعنا نقول أن العقد في المستوى السفلي للشجرة في الشكل 1 تمثل عناصر في مجموعة مصنفة. البحث الثنائي هو خوارزمية الفجوة والقهر ، ويوضح الرسم كيف سنحتاج إلى (على الأكثر) 4 مقارنات للعثور على السجل الذي نبحث عنه في مجموعة بيانات العناصر الـ 16 هذه.

افترض أن لدينا بدلاً من ذلك مجموعة بيانات بها 32 عنصرًا. تابع الرسم أعلاه لتجد أننا سنحتاج الآن إلى 5 مقارنات للعثور على ما نبحث عنه ، حيث أن الشجرة لم تنمو سوى مستوى واحد أعمق عندما قمنا بضرب كمية البيانات. نتيجة لذلك ، يمكن وصف تعقيد الخوارزمية كترتيب لوغاريتمي.

التخطيط log(n) على قطعة من الورق العادي ، سيؤدي إلى رسم بياني حيث يفلت صعود المنحنى n يزيد:

Answer 3

O(log N) يعني في الأساس الوقت يرتفع خطيًا بينما n يرتفع بشكل كبير. لذلك إذا استغرق الأمر 1 الثانية لحساب 10 عناصر ، سوف يستغرق الأمر 2 ثواني لحساب 100 عناصر، 3 ثواني لحساب 1000 عناصر ، وهلم جرا.

هو O(log n) عندما نقوم بتقسيم ونوع نوع الخوارزميات على سبيل المثال البحث الثنائي. مثال آخر هو النوع السريع حيث نقوم في كل مرة نقسم فيه الصفيف إلى جزأين وفي كل مرة يستغرقها O(N) حان الوقت للعثور على عنصر محوري. ومن هنا N O(log N)

Answer 4

التفسير أدناه هو استخدام حالة A Comple متوازن شجرة ثنائية لمساعدتك على فهم كيف نحصل على تعقيد الوقت اللوغاريتمي.

الشجرة الثنائية هي حالة تنقسم فيها مشكلة في الحجم إلى مشكل فرعي بحجم N/2 حتى نصل إلى مشكلة من الحجم 1:

وهكذا تحصل على o (log n) وهو مقدار العمل الذي يجب القيام به على الشجرة أعلاه للوصول إلى حل.

خوارزمية شائعة مع تعقيد الوقت O (log n) هي البحث الثنائي الذي تكون علاقته العودية t (n/2) + o (1) أي في كل مستوى لاحق من الشجرة التي تقسمها إلى نصف وتؤدي كمية ثابتة من العمل الإضافي.

Answer 5

ملخص

أعطى آخرون أمثلة مخطط جيد ، مثل مخططات الأشجار. لم أر أي أمثلة رمز بسيط. لذا ، بالإضافة إلى توضيحي ، سأقدم بعض الخوارزميات مع عبارات طباعة بسيطة لتوضيح تعقيد فئات الخوارزمية المختلفة.

أولاً ، ستحتاج إلى فكرة عامة عن اللوغاريتم ، والتي يمكنك الحصول عليها https://en.wikipedia.org/wiki/logarithm . استخدام العلوم الطبيعية e والسجل الطبيعي. سيستخدم التلاميذ الهندسيون log_10 (قاعدة السجل 10) وسيستخدم علماء الكمبيوتر log_2 (قاعدة السجل 2) كثيرًا ، لأن أجهزة الكمبيوتر قائمة على أساس ثنائي. في بعض الأحيان سترى اختصارات السجل الطبيعي كما ln(), ، عادةً ما يترك المهندسون _10 ويستخدمون فقط log() ويتم اختصار log_2 lg(). جميع أنواع اللوغاريتمات تنمو بطريقة مماثلة ، وهذا هو السبب في أنها تشترك في نفس الفئة log(n).

عندما تنظر إلى أمثلة التعليمات البرمجية أدناه ، أوصي بالنظر إلى O (1) ، ثم o (n) ، ثم o (n^2). بعد أن تكون جيدًا مع هؤلاء ، ثم انظر إلى الآخرين. لقد قمت بتضمين أمثلة نظيفة بالإضافة إلى اختلافات لتوضيح كيف يمكن أن تؤدي التغييرات الدقيقة إلى نفس التصنيف.

يمكنك التفكير في O (1) ، O (n) ، o (logn) ، إلخ كطبقات أو فئات من النمو. ستستغرق بعض الفئات وقتًا أكثر من غيرها. تساعد هذه الفئات في منحنا طريقة لطلب أداء الخوارزمية. نما بعض أسرع مع نمو المدخلات n. الجدول التالي يوضح النمو العددي. في الجدول أدناه ، فكر في السجل (N) باعتباره سقف log_2.

أمثلة رمز بسيطة لمختلف فئات O كبيرة:

س (1) - أمثلة زمنية ثابتة:

• الخوارزمية 1:

خوارزمية 1 يطبع مرحبًا مرة واحدة ولا يعتمد على n ، لذلك سيتم تشغيله دائمًا في وقت ثابت ، لذلك فهو كذلك O(1).

print "hello";

• الخوارزمية 2:

خوارزمية 2 مطبوعة مرحبا 3 مرات ، ومع ذلك لا يعتمد على حجم الإدخال. حتى مع نمو N ، ستطبع هذه الخوارزمية دائمًا Hello 3 مرات فقط. أن يقال 3 ، هو ثابت ، لذلك هذه الخوارزمية هي أيضا O(1).

print "hello";
print "hello";
print "hello";

o (سجل (ن)) - أمثلة لوغاريتمية:

• الخوارزمية 3 - هذا الأفعال مثل "log_2"

توضح الخوارزمية 3 خوارزمية تعمل في log_2 (n). لاحظ أن تشغيل ما بعد الحلقة يضاعف القيمة الحالية لـ I by 2 ، لذلك i يذهب من 1 إلى 2 إلى 4 إلى 8 إلى 16 إلى 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";

• الخوارزمية 4 - هذا الأفعال مثل "log_3"

الخوارزمية 4 توضح log_3. يلاحظ i يذهب من 1 إلى 3 إلى 9 إلى 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• الخوارزمية 5 - هذا يعمل مثل "log_1.02"

تعد الخوارزمية 5 مهمة ، حيث إنها تساعد في إظهار أنه طالما أن الرقم أكبر من 1 وتضرب النتيجة مرارًا وتكرارًا ، فأنت تبحث عن خوارزمية لوغاريتمية.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

س (ن) - أمثلة زمنية خطي:

• الخوارزمية 6

هذه الخوارزمية بسيطة ، والتي تطبع Hello n Times.

for(int i = 0; i < n; i++)
  print "hello";

• الخوارزمية 7

تُظهر هذه الخوارزمية تباينًا ، حيث ستطبع Hello N/2 مرات. n/2 = 1/2 * n. نتجاهل ثابت 1/2 ونرى أن هذه الخوارزمية هي O (N).

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n*log (n)) - أمثلة nlog (n):

• خوارزمية 8

فكر في هذا كمجموعة من O(log(n)) و O(n). إن تعشيش الحلقات تساعدنا في الحصول على O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";

• الخوارزمية 9

تشبه الخوارزمية 9 الخوارزمية 8 ، لكن كل من الحلقات سمحت بالتغيرات ، والتي لا تزال تؤدي إلى النتيجة النهائية O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (N^2) - N مربعة أمثلة:

• خوارزمية 10

O(n^2) يتم الحصول عليها بسهولة عن طريق التعشيش معيار للحلقات.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";

• الخوارزمية 11

مثل الخوارزمية 10 ، ولكن مع بعض الاختلافات.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n^3) - N Cubed Ampruments:

• خوارزمية 12

هذا مثل الخوارزمية 10 ، ولكن مع 3 حلقات بدلاً من 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";

• خوارزمية 13

مثل الخوارزمية 12 ، ولكن مع بعض الاختلافات التي لا تزال تسفر O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

ملخص

ما ورد أعلاه يعطي عدة أمثلة مستقيمة للأمام ، والتغيرات للمساعدة في إظهار التغييرات الدقيقة التي يمكن تقديمها والتي لا تغير التحليل حقًا. نأمل أن يمنحك رؤية كافية.

Answer 6

إذا كان لديك وظيفة تستغرق:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

ثم يستغرق السجل₂(ن) الوقت. ال تدوين كبير, ، يتحدث بشكل فضفاض ، أن العلاقة لا تحتاج إلا إلى أن تكون صحيحة بالنسبة إلى N كبيرة ، ويمكن تجاهل العوامل المستمرة والمصطلحات الأصغر.

Answer 7

وقت التشغيل اللوغاريتمي (O(log n)) يعني بشكل أساسي أن وقت التشغيل ينمو بما يتناسب مع لوغاريتم من حجم الإدخال - على سبيل المثال ، إذا كانت 10 عناصر تستغرق بعض الوقت على الأكثر x, و 100 عنصر يستغرق على الأكثر ، على سبيل المثال ، 2x, و 10000 عنصر يستغرق على الأكثر 4x, ، ثم يبدو مثل O(log n) تعقيد الوقت.

Answer 8

اللوغاريتم

حسنًا ، دعنا نحاول أن نفهم تمامًا ماهية لوغاريتم بالفعل.

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

الآن تخيل أن الحبل محاط بقطب. الحصان للابتعاد سيتعين عليه الآن أن يسحب عدة مرات أكثر صعوبة. يعتمد مقدار المرات على خشونة الحبل وحجم القطب ، ولكن لنفترض أنه سيضرب قوة المرء بمقدار 10 (عندما يقوم الحبل بدور كامل).

الآن إذا تم حلق الحبل مرة واحدة ، فسوف يحتاج الحصان إلى سحب 10 مرات أكثر صعوبة. إذا قرر الإنسان أن يجعل الأمر صعبًا على الحصان ، فقد يحلق الحبل مرة أخرى حول القطب ، مما يزيد من قوته بمقدار 10 مرات إضافية. ستقوم حلقة ثالثة مرة أخرى بزيادة القوة بمقدار 10 مرات.

يمكننا أن نرى أنه بالنسبة لكل حلقة ، تزداد القيمة بمقدار 10 1،000،000.

3 هي اللوغاريتم على 1000 ، و 6 هي اللوغاريتم من 1،000،000 (قاعدة 10).

إذن ماذا يعني O (log n) فعليًا؟

في مثالنا أعلاه ، "معدل النمو" هو س (سجل ن). لكل حلقة إضافية ، فإن القوة التي يمكن أن تتعاملها حبلنا هي 10 مرات أكثر:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

الآن ، استخدم المثال أعلاه قاعدة 10 ، ولكن لحسن الحظ ، فإن قاعدة السجل غير مهمة عندما نتحدث عن تدوين كبير.

الآن دعونا نتخيل أنك تحاول تخمين رقم بين 1-100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

الآن استغرق الأمر 7 تخمينات للحصول على هذا بشكل صحيح. لكن ما هي العلاقة هنا؟ ما هو أكبر عدد العناصر التي يمكنك تخمينها من كل تخمين إضافي؟

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

باستخدام الرسم البياني ، يمكننا أن نرى أنه إذا استخدمنا بحثًا ثنائيًا لتخمين رقم بين 1-100 ، فسوف يستغرق الأمر لنا في الغالب 7 محاولات. إذا كان لدينا 128 رقمًا ، فيمكننا أيضًا تخمين الرقم في 7 أحاولات ولكن 129 رقمًا سيأخذنا في الغالب 8 محاولات (في العلاقات مع اللوغاريتمات ، هنا نحتاج إلى 7 تخمينات لنطاق قيمة 128 ، 10 تخمينات لنطاق قيمة 1024. 7 هل هو لوغاريتم 128 ، 10 هو اللوغاريتم من 1024 (قاعدة 2)).

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

يمكننا أن نرى ذلك لكل تخمين مجموعة بياناتنا تتقلص. هناك قاعدة جيدة من الإبهام لتحديد ما إذا كانت الخوارزمية لديها وقت لوغاريتميات هي معرفة ما إذا كانت مجموعة البيانات تتقلص بترتيب معين بعد كل تكرار

ماذا عن o (n log n)؟

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

يمكنك بسهولة تحديد ما إذا كان الوقت الخوارزمي هو n log n. ابحث عن حلقة خارجية تكرر من خلال قائمة (O (N)). ثم انظر لمعرفة ما إذا كانت هناك حلقة داخلية. إذا كانت الحلقة الداخلية قطع/تقليل مجموعة البيانات على كل تكرار ، تلك الحلقة هي (O (log n) ، وبالتالي الخوارزمية الكلية هي = o (n log n).

إخلاء المسئولية: تم الاستيلاء كتاب فرحة عالم الرياضيات من قبل و..

Answer 9

يمكنك التفكير في O (log n) بشكل حدسي من خلال قول الوقت يتناسب مع عدد الأرقام في N.

إذا كانت العملية تؤدي وقتًا ثابتًا في كل رقم أو بت من المدخلات ، فستستغرق العملية بأكملها وقتًا يتناسب مع عدد الأرقام أو البتات في الإدخال ، وليس حجم الإدخال ؛ وبالتالي ، o (log n) بدلاً من o (n).

إذا اتخذت عملية ما سلسلة من القرارات الزمنية الثابتة ، فإن كل منها نصفي (يقلل بعامل 3 ، 4 ، 5 ..) حجم المدخل ، قاعدة 4 ، قاعدة 5 ...) من حجم n من المدخلات ، بدلاً من أن تكون o (n).

وهلم جرا.

Answer 10

أفضل طريقة كان علي دائمًا تصور خوارزمية عقلية تعمل في O (log n) كما يلي:

إذا قمت بزيادة حجم المشكلة بمقدار مضاعف (أي اضرب حجمه بمقدار 10) ، يتم زيادة العمل فقط بمقدار إضافي.

تطبيق هذا على سؤال الشجرة الثنائية الخاصة بك بحيث يكون لديك تطبيق جيد: إذا كنت مضاعفة عدد العقد في شجرة ثنائية ، يزداد الارتفاع فقط بمقدار 1 (كمية مضافة). إذا كنت مضاعفة مرة أخرى ، فإنه لا يزال يزداد بنسبة 1. (من الواضح أنني أفترض أنه يبقى متوازناً وما إلى ذلك). وبهذه الطريقة ، بدلاً من مضاعفة عملك عندما يتضاعف حجم المشكلة ، فأنت تقوم فقط بمزيد من العمل قليلاً. لهذا السبب خوارزميات O (log n) رائعة.

Answer 11

أولاً أوصيك بقراءة الكتاب التالي ؛

الخوارزميات (الطبعة الرابعة)

فيما يلي بعض الوظائف وتعقيداتها المتوقعة. تشير الأرقام ترددات تنفيذ البيان.

التالية مخطط التعقيد الكبير مأخوذة أيضا من Bigocheateset

أخيرًا معرضًا بسيطًا للغاية ، هناك يوضح كيف يتم حسابه ؛

تشريح ترددات تنفيذ بيان البرنامج.

تحليل وقت تشغيل البرنامج (مثال).

Answer 12

ما هو السجل_ب(ن)؟

إنه عدد المرات التي يمكنك فيها قطع سجل الطول n بشكل متكرر إلى أجزاء متساوية B قبل الوصول إلى قسم من الحجم 1.

Answer 13

تقسيم الخوارزميات وقهرها عادة logn مكون لوقت التشغيل. هذا يأتي من النصف المتكرر من المدخلات.

في حالة البحث الثنائي ، كل تكرار ترميه نصف المدخلات. تجدر الإشارة إلى أنه في تدوين Big-O ، سجل قاعدة 2.

تحرير: كما لوحظ ، لا يهم قاعدة السجل ، ولكن عند استخلاص الأداء الكبير للخوارزمية ، سيأتي عامل السجل من النصف ، ولهذا السبب أفكر في الأمر كـ قاعدة 2.

Answer 14

ولكن ما هو بالضبط o (log n)؟ على سبيل المثال ، ماذا يعني القول أن ارتفاع الشجرة الثنائية الكاملة هو o (log n)؟

أود إعادة صياغة هذا على أنه "ارتفاع شجرة ثنائية كاملة هو log n '. سيكون اكتشاف ارتفاع شجرة ثنائية كاملة O (سجل N) ، إذا كنت تتجاوز خطوة بخطوة.

لا أستطيع أن أفهم كيفية تحديد وظيفة مع وقت لوغاريتمي.

اللوغاريتم هي أساسا عكس الأسعار. لذلك ، إذا كانت كل "خطوة" من وظيفتك تزيل أ عامل من عناصر من مجموعة العناصر الأصلية ، وهي خوارزمية زمنية لوغاريتمية.

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

Answer 15

ستستغرق هاتان الحالات 2 وقتًا

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

Answer 16

O(log n) يشير إلى وظيفة (أو خوارزمية ، أو خطوة في خوارزمية) تعمل في فترة زمنية تتناسب مع اللوغاريتم (عادةً ما تكون قاعدة 2 في معظم الحالات ، ولكن ليس دائمًا ، وعلى أي حال ، هذا غير مهم من خلال تدوين كبير*) من حجم المدخلات.

الوظيفة اللوغاريتمية هي عكس الوظيفة الأسية. بعبارة أخرى ، إذا كانت مدخلاتك تنمو بشكل كبير (وليس خطيًا ، كما ستعتبرها عادةً) ، تنمو وظيفتك خطيًا.

O(log n) تعتبر أوقات التشغيل شائعة جدًا في أي نوع من تطبيقات الفجوة والقهر ، لأنك (مثالي) تقطع العمل إلى نصفين في كل مرة. إذا كنت تقوم في كل خطوات من القسم أو التغلب ، فأنت تقوم بعمل مستمر للوقت (أو العمل ليس وقتًا ثابتًا ، ولكن مع مرور الوقت ينمو بشكل أبطأ من O(log n)) ، ثم وظيفتك بأكملها O(log n). من الشائع إلى حد ما أن يكون كل خطوة تتطلب وقتًا خطيًا في الإدخال بدلاً من ذلك ؛ هذا سوف يصل إلى إجمالي التعقيد الزمني O(n log n).

تعقيد وقت التشغيل للبحث الثنائي هو مثال على O(log n). هذا لأنه في البحث الثنائي ، تتجاهل دائمًا نصف مدخلاتك في كل خطوة لاحقة من خلال تقسيم الصفيف إلى النصف وتركز فقط على نصف مع كل خطوة. تكون كل خطوة وقتًا ثابتًا ، لأنه في البحث الثنائي ، تحتاج فقط إلى مقارنة عنصر واحد بمفتاحك لمعرفة ما يجب القيام به بعد ذلك من عدم وجود مجموعة كبيرة من الصفيف الذي تفكر فيه في أي وقت. لذلك يمكنك القيام بخطوات سجل (N)/LOG (2) تقريبًا.

تعقيد وقت التشغيل من نوع الدمج هو مثال على O(n log n). هذا لأنك تقسم الصفيف إلى نصفين مع كل خطوة ، مما يؤدي إلى ما مجموعه تقريبًا خطوات السجل (N)/LOG (2). ومع ذلك ، في كل خطوة ، تحتاج إلى إجراء عمليات دمج على جميع العناصر (سواء كانت عملية دمج واحدة على اثنين من العناصر الفرعية من عناصر N/2 ، أو عمليتين دمج على أربعة من عناصر N/4 ، غير ذي صلة لأنها تضيف إلى الاضطرار إلى ذلك افعل هذا لعناصر n في كل خطوة). وبالتالي ، فإن التعقيد الكلي هو O(n log n).

*تذكر هذا التدوين الكبير ، حسب التعريف, ، الثوابت لا تهم. أيضا من قبل تغيير قاعدة الأساس بالنسبة إلى اللوغاريتمات ، فإن الفرق الوحيد بين اللوغاريتمات من القواعد المختلفة هو عامل ثابت.

Answer 17

o (log n) مضللة بعض الشيء ، بشكل أكثر دقة o (سجل₂ ن) ، أي (لوغاريتم مع قاعدة 2).

ارتفاع شجرة ثنائية متوازنة هو o (سجل₂ ن) ، لأن كل عقدة لديها اثنين (لاحظ "اثنين" كما في السجل₂ ن) العقد الفرعية. لذلك ، فإن شجرة مع عقد n لها ارتفاع السجل₂ ن.

مثال آخر هو البحث الثنائي ، الذي لديه وقت تشغيل O (سجل₂ ن) لأنه في كل خطوة تقسم مساحة البحث على 2.

Answer 18

هذا يعني ببساطة أن الوقت اللازم لهذه المهمة ينمو مع السجل (n) (مثال: 2s لـ n = 10 ، 4s لـ n = 100 ، ...). اقرأ مقالات ويكيبيديا خوارزمية البحث الثنائي و تدوين كبير لمزيد من الدقة.

Answer 19

ببساطة: في كل خطوة من خوارزميةك ، يمكنك قطع العمل إلى النصف. (ما يعادل غير مقارب للثالث ، الرابع ، ...)

Answer 20

إذا قمت برسم وظيفة لوغاريتمية على آلة حاسبة رسومية أو شيء مشابه ، فسترى أنه يرتفع ببطء شديد - ببطء أكثر من وظيفة خطية.

هذا هو السبب في أن الخوارزميات ذات التعقيد الزمني اللوغاريتمي يتم البحث عنها بشكل كبير: حتى بالنسبة إلى N Big N (دعنا نقول n = 10^8 ، على سبيل المثال) ، فإنها تؤدي أكثر من مقبول.

Answer 21

ولكن ما هو بالضبط o (log n)

ما يعنيه بالضبط هو "كما n يميل نحو infinity, ، ال time يميل نحو a*log(n) أين a هو عامل التحجيم الثابت ".

أو في الواقع ، هذا لا يعني ذلك تمامًا ؛ على الأرجح يعني شيئًا مثل "time مقسوما a*log(n) يميل نحو 1".

"تميل نحو" لديه المعنى الرياضي المعتاد من "التحليل": على سبيل المثال ، ذلك "إذا اخترت أي ثابت غير صفري صغير بشكل تعسفي k, ، ثم يمكنني العثور على قيمة مقابلة X مثل ذلك ((time/(a*log(n))) - 1) اقل من k لجميع قيم n أكثر من X."

---

من حيث العلماء ، فهذا يعني أن المعادلة للوقت قد تحتوي على بعض المكونات الأخرى: على سبيل المثال قد يكون لها وقت بدء تشغيل ثابت ؛ لكن هذه المكونات الأخرى شاحبة نحو عدم الأهمية بالنسبة للقيم الكبيرة لـ N ، وسجل A*هو المصطلح المهيمن على N كبير.

لاحظ أنه إذا كانت المعادلة ، على سبيل المثال ...

الوقت (ن) = أ + بسجل (ن) + جن + دنن

... ثم سيكون هذا o (n مربع) لأنه ، بغض النظر عن قيم الثوابت A و B و C و غير الصفر D ، d*n*n سوف يهيمن المصطلح دائمًا على الآخرين على أي قيمة كبيرة بما فيه الكفاية من n.

هذا ما يعنيه تدوين البت: إنه "ما هو ترتيب المصطلح المهيمن لأي N كبير بما فيه الكفاية".

Answer 22

يمكنني إضافة شيء مثير للاهتمام ، أقرأه في كتاب من قبل Kormen وما إلى ذلك منذ وقت طويل. الآن ، تخيل مشكلة ، حيث يتعين علينا إيجاد حل في مساحة مشكلة. يجب أن تكون مساحة المشكلة هذه محدودة.

الآن ، إذا كنت تستطيع أن تثبت ، في كل تكرار لخوارزميةك ، قطعت جزءًا صغيرًا من هذه المساحة ، وهذا لا يقل عن حد ما ، وهذا يعني أن الخوارزمية الخاصة بك تعمل في وقت O (logn).

يجب أن أشير إلى أننا نتحدث هنا عن حد الكسر النسبي ، وليس المطلق. البحث الثنائي هو مثال كلاسيكي. في كل خطوة نرمي 1/2 من مساحة المشكلة. لكن البحث الثنائي ليس هو المثال الوحيد. لنفترض ، لقد أثبتت بطريقة ما ، أنه في كل خطوة ترميها على الأقل 1/128 من مساحة المشكلة. هذا يعني أن البرنامج لا يزال يعمل في وقت O (logn) ، على الرغم من أنه أبطأ بكثير من البحث الثنائي. هذا تلميح جيد للغاية في تحليل الخوارزميات العودية. غالبًا ما يمكن إثبات أنه في كل خطوة لن تستخدم العودة عدة متغيرات ، وهذا يؤدي إلى قطع بعض الكسر في مساحة المشكلة.

Answer 23

يمكنني إعطاء مثال على حلقة ، وربما بمجرد فهم المفهوم ، ربما سيكون من الأسهل فهم في سياقات مختلفة.

هذا يعني أنه في الحلقة تنمو الخطوة بشكل كبير. على سبيل المثال

for (i=1; i<=n; i=i*2) {;}

التعقيد في O-Notation لهذا البرنامج هو O (السجل (N)). دعنا نحاول أن نحلق من خلالها باليد (ن ما بين 512 و 1023 (باستثناء 1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

على الرغم من أن N في مكان ما بين 512 و 1023 ، إلا أن 10 تكرارات فقط تحدث. وذلك لأن الخطوة في الحلقة تنمو بشكل كبير وبالتالي لا تستغرق سوى 10 تكرارات للوصول إلى الإنهاء.

لوغاريتم x (إلى قاعدة a) هي الوظيفة العكسية لـ^x.

إنه مثل القول بأن اللوغاريتم هو عكس الأسي.

حاول الآن رؤيتها بهذه الطريقة ، إذا كان الأسي يزداد بسرعة كبيرة ، فإن اللوغاريتم ينمو (عكسيا) بطيئًا جدًا.

الفرق بين O (n) و o (log (n)) ضخمة ، على غرار الفرق بين o (n) و o (a^n) (a ثابت).

Answer 24

في كل مرة نكتب فيها خوارزمية أو رمز نحاول تحليل تعقيدها المقارب. إنه مختلف عن تعقيد الوقت.

التعقيد المقارب هو سلوك وقت تنفيذ الخوارزمية في حين أن التعقيد الزمني هو وقت التنفيذ الفعلي. لكن بعض الناس يستخدمون هذه المصطلحات بالتبادل.

لأن تعقيد الوقت يعتمد على المعلمات المختلفة بمعنى.
1. النظام الفيزيائي
2. لغة البرمجة
3. نمط الترميز
4. وأكثر من ذلك بكثير ......

إن وقت التنفيذ الفعلي ليس مقياسًا جيدًا للتحليل.

بدلاً من ذلك ، نأخذ حجم الإدخال مثل المعلمة لأنه مهما كان الرمز ، فإن الإدخال هو نفسه.وبالتالي فإن وقت التنفيذ هو وظيفة حجم الإدخال.

فيما يلي مثال على خوارزمية الوقت الخطي

البحث الخطي
بالنظر إلى عناصر الإدخال n ، للبحث عن عنصر في الصفيف الذي تحتاجه في معظم المقارنات 'n'. بمعنى آخر ، بغض النظر عن لغة البرمجة التي تستخدمها ، ونمط الترميز الذي تفضله ، على النظام الذي تنفذه. في أسوأ السيناريو ، يتطلب الأمر فقط مقارنات N.

وليس فقط البحث ، أيا كان العمل (الزيادة أو المقارنة أو أي عملية) وظيفة من حجم الإدخال.

لذلك عندما تقول أن أي خوارزمية هي o (log n) ، فهذا يعني أن وقت التنفيذ هو أوقات سجل حجم الإدخال n.

مع زيادة حجم الإدخال من العمل المنجز (هنا يزداد وقت التنفيذ). (وبالتالي التناسب)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

انظر مع زيادة حجم الإدخال ، يتم زيادة العمل المنجز وهو مستقل عن أي آلة. وإذا حاولت معرفة قيمة وحدات العمل ، فإنها تعتمد فعليًا على المعلمات المحددة أعلاه. فسيتغير وفقًا للأنظمة وجميعها.

Answer 25

log x to base b = y هو عكس b^y = x

إذا كان لديك شجرة M-ary من العمق D والحجم N ، ثم:

• اجتياز الشجرة بأكملها ~ o (m^d) = o (n)

• المشي مسارًا واحدًا في الشجرة ~ o (d) = o (سجل n إلى قاعدة m)

Answer 26

في تكنولوجيا المعلومات ، يعني ذلك:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

النملة يبدو أن هذا التدوين قد أخذ في الغالب من الرياضيات.

في هذه المقالة هناك اقتباس:De Knuth ، "Big Omicron و Big Omega و Big Theta" ، 1976:

على أساس القضايا التي تمت مناقشتها هنا ، أقترح أن يعتمد أعضاء SIGACT ، ومحرري مجلات علوم الكمبيوتر والرياضيات ، رموزًا على النحو المحدد أعلاه ، ما لم يمكن العثور على بديل أفضل بشكل معقول قريبًا.

اليوم هو عام 2016 ، لكننا نستخدمه اليوم.

---

في التحليل الرياضي يعني:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

ولكن حتى في التحليل الرياضي في بعض الأحيان تم استخدام هذا الرمز في المعنى "C*G (n)> f (n)> 0".

كما أعرف من الجامعة ، تم إنتاج الرمز من قبل عالم الرياضيات الألماني لانداو (1877-1938)

Answer 27

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

في الخطوة الأولى ، يمكنك الانقسام على 2. بعد ذلك لديك قوائمان (2^1) ، يمكنك تقسيم كل منها على 2 ، حتى يكون لديك 4 قوائم (2^2) ، يمكنك الانقسام مرة أخرى ، لديك 8 قوائم (2^3 ) وهكذا حتى يكون حجم القائمة 1 1

هذا يمنحك المعادلة:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(تأخذ LG من كل جانب ، LG كونه قاعدة السجل 2)

Answer 28

إذا كنت تبحث عن إجابة تعتمد على الحدس ، فأود أن أضع تفسيرين لك.

1. تخيل تلة عالية جدا مع قاعدة واسعة جدا أيضا. للوصول إلى الجزء العلوي من التل ، هناك طريقتان: إحداهما مسار مخصص يتجول حول التل في الأعلى ، والآخر: شرفة صغيرة مثل المنحوتات مقطوعة لتوفير درج. الآن إذا كانت الطريقة الأولى تصل في الوقت الخطي O (n) ، فإن الثانية هي O (log n).

2. تخيل خوارزمية ، تقبل عدد صحيح ، n كمدخلات ويكمل في الوقت المناسب مع n ثم هو o (n) أو theta (n) ولكن إذا تم تشغيله في الوقت المناسب إلى number of digits or the number of bits in the binary representation on number ثم تعمل الخوارزمية في وقت O (log n) أو theta (log n).

Answer 29

المثال الثنائي الكامل هو o (ln n) لأن البحث يبدو مثل:

1 2 3 4 5 6 7 8 9 10 11 12

البحث عن 4 عوائد 3 مرات: 6 ، 3 ثم 4. و log2 12 = 3 ، وهو أمر جيد لعدد الزيارات عند الحاجة.

Answer 30

الخوارزميات في نموذج الفجوة والقهر هي من التعقيد O (logn). مثال واحد هنا ، احسب وظيفة الطاقة الخاصة بك ،

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

من http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/