ما هو يا كبير التدوين؟ -هل تستخدمه ؟ [مكررة]

Question

هذا السؤال سبق الجواب هنا:

• ما هو سهل الانجليزية شرح "يا كبير" التدوين؟ - 39 إجابات

ما هو يا كبير التدوين؟ -هل تستخدمه ؟

لقد غاب عن هذه الجامعة من الدرجة أعتقد :D

لا أحد استخدامه وإعطاء بعض أمثلة واقعية من حيث استخدامها ؟

---

انظر أيضا:

Big-O لمدة ثماني سنوات?
يا كبير, كيف يتم حساب/التقريبية ؟
هل تطبيق نظرية التعقيد الحسابي في الحياة الحقيقية ؟

Answer 1

شيء واحد مهم ينسى معظم الناس عندما نتحدث عن Big-O, وبالتالي لا يشعر بحاجة إلى أن أذكر أن:

لا يمكنك استخدام Big-O مقارنة السرعة اثنين من خوارزميات.Big-O يقول فقط كيف أبطأ بكثير خوارزمية سوف تحصل على (تقريبا) إذا ضعف عدد من البنود أو معالجتها أو كيف أسرع بكثير سوف تحصل إذا كنت خفض العدد إلى النصف.

ومع ذلك, إذا كان لديك اثنين مختلفة تماما خوارزميات واحد (A) هو O(n^2) والآخر (B) هو O(log n), هو لم يقل ذلك A أبطأ من B.في الواقع, مع 100 البنود ، A قد تكون عشر مرات أسرع من B.إلا أنه يقول أنه مع 200 قطعة ، A سوف تنمو أبطأ من قبل عامل n^2 و B سوف تنمو أبطأ من قبل عامل log n.لذا ، إذا كنت القياسي على حد سواء و أنت تعرف كم من الوقت A يشارك 100 البنود, وكم من الوقت B يحتاج لنفس 100 سلعة ، A هو أسرع من B, يمكنك حساب في أي كمية من المواد B ستتفوق A في السرعة (سرعة B يقلل أبطأ بكثير من واحد من A, ، وسوف تتفوق A عاجلا أو آجلا—وهذا هو بالتأكيد).

Answer 2

يا كبير التدوين يدل على عامل يحد من خوارزمية.في تبسيط تعبير عن كيف تشغيل خوارزمية المقاييس فيما يتعلق الإدخال.

على سبيل المثال (في جاوة):

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

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

هذا يعني أنك سوف تكون نسخ الرسالة الأولى n مرات حيث n هو عدد الأحرف في المدخلات.سوف يكون نسخ الحرف n-1 مرات, حتى في المجموع سيكون هناك (n-1)(n/2) نسخ.

هذا هو (n^2-n)/2 و يا كبير التدوين نحن فقط استخدام أعلى درجات عامل (عادة) وإسقاط أي الثوابت التي تتضاعف بها و نحن في نهاية المطاف مع O(n^2).

وذلك باستخدام ما يشبه StringBuilder سوف يكون على غرار O(nLog(n)).إذا كان لك حساب عدد الأحرف في بداية وتعيين قدرة StringBuilder يمكنك الحصول على أن يكون O(n).

حتى إذا كان لدينا 1000 حرف من المدخلات المثال الأول تنفيذ ما يقرب من مليون العمليات ، StringBuilder من شأنها أن تؤدي 10,000 ، StringBuilder مع setCapacity من شأنها أن تؤدي 1000 العمليات أن تفعل الشيء نفسه.هذا هو تقدير تقريبي ، ولكن O(n) التدوين هو عن أوامر من المقادير ، وليس بالضبط وقت التشغيل.

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

Answer 3

مشابهة جدا سؤال تم بالفعل طلب في Big-O لمدة ثماني سنوات?.نأمل أن الأجوبة ستكون هناك إجابة سؤالك على الرغم من أن سؤال السائل هل هناك قليلا من المعرفة الرياضية حول كل شيء الذي قد لا يكون لديك حتى توضيح إذا كنت بحاجة إلى شرح أشمل.

Answer 4

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

1) هذا أمر من قياس كفاءة خوارزمية عند العمل على بنية البيانات.

2) إجراءات مثل 'إضافة' / 'نوع' / 'إزالة' يمكن أن تأخذ كميات مختلفة من الوقت مع مختلف هياكل البيانات (الخوارزميات) ، على سبيل المثال "إضافة" و "إيجاد" هي O(1) ، hashmap ، ولكن O(log n) على شجرة ثنائية.نوع O(nlog ن) عن فرز سريع ، ولكن O(n^2) BubbleSort ، عند التعامل مع عادي الصفيف.

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

نعم إنها أكثر تعقيدا من ذلك.إذا كنت مهتما حقا في الحصول على الكتب المدرسية.

Answer 5

'Big-O' التدوين يستخدم لمقارنة معدلات النمو اثنين من وظائف متغير (أقول n) حيث n يحصل كبيرة جدا.إذا كانت الدالة f ينمو بسرعة أكبر بكثير من وظيفة ز نقول أن g = O(f) تعني أن الكبيرة ما يكفي n, و سوف دائما يكون أكبر من غرام إلى عامل القياس.

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

هذا النص ، أن ن يحصل كبيرة بما فيه الكفاية ، يسمح لنا أن سحب الكثير من الحيل المفيدة.وربما كان الأكثر استخداما هو واحد التي يمكنك تبسيط المهام أسفل إلى الأسرع نموا من حيث.على سبيل المثال n^2 + n = O(n^2) لأنه كما ن يحصل كبيرة بما فيه الكفاية ، ن^2 الأجل يحصل حتى أكبر من ذلك بكثير من ن أن ن المصطلح عمليا تافهة.لذا علينا أن نسقط من الاعتبار.

بيد أن ذلك لا يعني big-O التدوين هو أقل فائدة الصغيرة n, لأن تباطؤ النمو حيث أننا قد نسيت لا تزال كبيرة بما يكفي للتأثير على وقت التشغيل.

ما لدينا الآن هو أداة لمقارنة تكاليف اثنين من خوارزميات مختلفة ، اختصار أقول أن أحد أسرع أو أبطأ من غيرها.Big-O التدوين يمكن أن يساء استخدامها وهو عار كما هو غير دقيقة بما فيه الكفاية!هناك ما يعادل حيث تقول أن وظيفة ينمو بسرعة أقل من آخر ، أن اثنين من وظائف النمو بنفس المعدل.

هل يمكنني استخدامه ؟ نعم, في كل وقت - عندما أكون في معرفة مدى كفاءة قانون بلدي هو أنه يعطي العظيم 'الخلفي من المغلف - تقريب تكلفة.

Answer 6

إن "Intuitition" خلف Big-O

تخيل "المنافسة" بين وظيفتين على x عندما تقترب x إنفينيتي:f(x) و g(x).

الآن, إذا كان من النقطة (س) دالة واحدة دائما على أعلى قيمة ثم أخرى ثم دعونا استدعاء هذه الدالة "أسرع" من جهة أخرى.

لذلك ، على سبيل المثال ، إذا كان لكل x > 100 ترى أن f(x) > g(x) ثم f(x) هو "أسرع" مما g(x).

في هذه الحالة نقول g(x) = O(f(x)).f(x) يشكل نوعا من "الحد الأقصى للسرعة" من نوع g(x) ، منذ نهاية المطاف يمر ويترك خلف لخير.

ليس هذا بالضبط تعريف big-O التدوين, الذي ينص أيضا على أن f(x) فقط يجب أن يكون أكبر من C*g(x) على بعض ثابت C (الذي هو مجرد طريقة أخرى للقول أنه لا يمكن أن تساعد g(x) الفوز في المنافسة من خلال ضرب من قبل عامل ثابت - f(x) سوف يفوز دائما في النهاية).التعريف الرسمي كما يستخدم القيم المطلقة.ولكن أتمنى أن تمكنت من جعله بديهية.

Answer 7

كما قد يكون من المفيد النظر في أن تعقد العديد من خوارزميات أكثر من متغير واحد ، لا سيما في متعدد الأبعاد المشاكل.على سبيل المثال, وقد أتيحت لي مؤخرا كتابة الخوارزمية التالية.بالنظر إلى مجموعة من ن النقاط ، م المضلعات, استخراج جميع النقاط التي تقع في أي من المضلعات.التعقيد هو القائم حول اثنين من المتغيرات المعروفة ، ن م ، و معروف كيف العديد من النقاط في كل مضلع.يا كبير التدوين هنا هو قليلا جدا أكثر مما O(f(n)) أو حتى O(f(n) + g(m)).يا كبير هو جيد عند التعامل مع أعداد كبيرة من متجانسة العناصر ، ولكن لا نتوقع أن يكون الحال دائما.

من الجدير بالذكر أيضا أن العدد الفعلي التكرار على البيانات التي غالبا ما تعتمد على البيانات.فرز سريع عادة ما تكون سريعة ، presorted البيانات وأنه يبطئ.نقاطي و المضلعات alogorithm انتهى سريع جدا ، على مقربة من O(n + (م سجل(م)) ، على أساس المعرفة المسبقة البيانات من المرجح أن يكون تنظيم الأحجام النسبية n و m.سوف تسقط بشدة على عشوائيا تنظيم البيانات من مختلف الأحجام النسبية.

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

Answer 8

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

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

Answer 9

ما هو يا كبير التدوين؟ -

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

لا يا كبير التدوين؟ -

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

أمثلة ملموسة?

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

Answer 10

من ويكيبيديا.....

يا كبير التدوين مفيد عند تحليل الخوارزميات الكفاءة.على سبيل المثال ، في الوقت (أو عدد الخطوات) يستغرقه لإكمال مشكلة حجم n قد تكون وجدت لتكون T(n) = 4n2 − 2n + 2.

كما ن ينمو كبيرة ، n2 الأجل سوف تأتي إلى الهيمنة ، حيث أن جميع شروط أخرى يمكن أن تكون مهملة — على سبيل المثال عندما ن = 500, مصطلح 4n2 1000 مرة كبيرة مثل 2n الأجل.تجاهل هذا الأخير سيكون لها تأثير يذكر على التعبير قيمة بالنسبة لمعظم الأغراض.

من الواضح أنني لم يسبق استخدامها..

Answer 11

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

Answer 12

يقول عدد التكرارات خوارزمية في أسوأ الأحوال.

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

دعنا نقول أن هناك ن العناصر في القائمة.في أسوأ الأحوال تأخذ n التكرار.في يا كبير notiation فمن O(n).

يقول factualy مدى كفاءة خوارزمية.