تدوين كبير للتعبير

Question

إذا كان لدي خوارزمية تستغرق 4N^2 + 7N تتحرك لإنجازها ، فما هو O؟ س (4N^2)؟ س (ن^2)؟

أعلم أن 7N مقطوع ، لكنني لا أعرف ما إذا كان ينبغي علي الاحتفاظ بمعامل N^2 أم لا.

شكرًا

Answer 1

يجب عليك إسقاط أي معاملات لأن السؤال يسأل حقًا "بترتيب" ، والذي يحاول وصفه بأنه خطي ، أسي ، لوغاريتمي ، إلخ ... أي عندما يكون N كبيرًا جدًا ، فإن المعامل لا يقل أهمية.

وهذا ما يفسر أيضًا سبب إسقاط +7n ، لأنه عندما يكون N كبيرًا جدًا ، فإن هذا المصطلح له أهمية ضئيلة نسبيًا للإجابة النهائية. إذا كنت معتادًا على حساب التفاضل والتكامل ، فقد تقول lim n-> inf (4*n^2+7n) ~ = lim n-> inf (4*n^2) ~ = lim n-> inf (n^2)

يمكنك أيضًا التفكير في هذا الأمر بالمعنى الرسومي ... أي إذا قمت برسم الوظيفة 4N^2 + 7N لقيم أكبر وأكبر لـ N ، فقد يقول عالم الرياضيات "يبدو وكأنه n^2". منحت ، يجب أن تكون عالم رياضيات ليبرالي إلى حد ما ، لأن هذا ليس بيانًا صارمًا ، لكن هذا ما تحاول نقله (...) بشكل أساسي.

Answer 2

المعاملات ليست ذات صلة بالترميز الكبير ، لذلك فهي فقط (ن²). كما يوضح ويكيبيديا:

...] تصبح المعاملات غير ذات صلة إذا قارنا بأي ترتيب آخر للتعبير ، مثل التعبير الذي يحتوي على مصطلح N.³ أو ن².

Answer 3

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

لتبسيط (الكثير) ، دع f و g يكون وظيفتين f : N -> N و g : N -> N. نقول ذلك f is O(g) إذا وفقط إذا كان هناك ثابت M > 0 مثل ذلك |f(n)| < M|g(n)|, ، للجميع n > M. هذا هو ، بشكل غير رسمي ، بدءا من قيمة كبيرة n, ، كل القيم f(n) أصغر من مضاعف g(n) (بمعنى آخر، g ينمو أسرع من f).

هذا التعريف يعادل

f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K

لذلك ، دعونا نأخذ f(n) = 4n^2 + 7n و g(n) = n^2, ومحاولة إثبات f is O(g) (سوف أغفل {n -> +oo}):

lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
                  = 4 + lim 7/n = 4 + 0 = 4

هذا يعني أن هناك M مثل ذلك n > M ==> |f(n)| < M|g(n)|, ، وبالتالي f is O(g).

من الناحية الفنية من الصحيح أن نقول 4n^2 + 7n is O(4n^2), ، كما هو صحيح أن أقول 4n^2 + 7n is O(n^3), 4n^2 + 7n is O(e^n), ، وهلم جرا. ولكن لكي نكون ذا معنى ، نحن مهتمون بالحد الأدنى. حتى إذا f is O(e^n) و f is O(n^2), ، نحن مهتمون أكثر بمعرفة ذلك f is O(n^2), ، لأن هذا أكثر تقييدا.

ملاحظة مهمة جدا

ما هو مهم عند اختيار خوارزمية هو فهم ذلك الرموز الكبيرة يعود الى الحالات المقاربة, هذا هو ، عندما تفكر مدخلات ضخمة للغاية لا يمكن تصورها, ، يمكن أن تتجاوز الطاقة الحسابية المتاحة في الكون المعروف (أي مجموعات الإدخال اللانهائية ، معبراً عنها رياضيا {n -> +oo}).

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

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

Answer 4

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

Answer 5

بيان مثل

4n² + 7n = O(n²)

يعني أنه بالنسبة لبعض المضاعف الثابت c, ، التعبير cn² سوف تتجاوز في النهاية 4n² + 7n. من غير الصحيح من الناحية الفنية ترك المعامل هناك - O(n²) و O(4n²) يعني نفس الشيء بالضبط ، لأن أي ثابت c يمكن استبدال السابق c/4 لهذا الأخير. ومع ذلك ، فإن مثل هذا الشيء أقل وضوحًا ، وربما مضللاً ، وبالتأكيد غير القياسي.

Answer 6

من الناحية الرياضية ، سوف تكتب o (4n²). وهذا يعني أن وظيفة تعقيد الخوارزميات الخاصة بك تتصرف كـ N-> 4n² نحو Infinite الإيجابية.

ولكن في علوم الكمبيوتر/الخوارزمية ، ستكتب فقط O (n²) ، وهو ما يكفي لتصنيف الخوارزمية الخاصة بك.