SUM SECT ل Big-O مع وظائف تعقيد متساوية؟

Question

خاصية واحدة من Big-etation هي SUM SULE ، والتي تنص على أنه عندما يكون لدي وظيفتان $ f_1 $ $ f_2 $ ووظائف التعقيد المقابلة لها $ g_1 $ و $ g_2 $ ، ثم التعقيد المشترك هو $ f_1 + f_2= o (\ max (g_1، g_2) $ .

ولكن ماذا نختار ما إذا كانت كلا مهام التعقيد متساوية؟ على سبيل المثال، إذا $ f_1 (n) $ هي فرز صفيف و $ _ f2 (m) $ كذلك، فإن التعقيدات هي $ O (n \ log (n)) $ و $ O (m \ log ( م)) $ . سيكون تطبيق القاعدة $ o (\ max (n \ log (n)، m \ log (m))) $ . أعتقد أن اختيار أي من هؤلاء من شأنه أن يؤدي إلى تقدير صالح ولكنه غير صحيح للغاية كما كنت تسقط متغير واحد. إلى جانب ذلك، ليس من الواضح أي واحد لاختيار.

هل هي الحالة التي ليس من المفترض أن تستخدمها القاعدة عند وجود متغيرات متعددة؟

Answer 1

يعتمد ذلك على ما إذا كانت بعض المتغيرات بشأن معتمدة على آخر، أو إذا تم تقديمها كمعلمات في المشكلة. على سبيل المثال، في العديد من المشكلات المتعلقة الرسم البياني، $ n $ يمكن أن يكون عدد الرأس، و $ m $ يمكن أن يكون عدد الحواف. في هذه الحالة، $ M $ يمكن أن يكون كبيرا مثل $ O (n ^ 2) $ . لذلك في الحالة العامة، قل إذا كان لدينا خوارزمية تعمل المرحلة الأولى في $ O (n) $ (n) $ يعمل المرحلة الثانية في $ O (M) $ ، نحن فقط أضف المصطلحين معا ولا تحاول التبسيطين --- وقت التشغيل النهائي هو $ O (N + M) $ .

من حيث العديد من المتغيرات التي تعطى كمعلمات غير مرتبطة بالضرورة: إيلات المتغيرات المتعددة داخل المعادلة النهائية هي المعايير، على سبيل المثال أستطيع أن أقول أن ضرب $ m \ times n $ matrix و $ n \ times p $ matrix يأخذ $ o (mnp) $ - -Time باستخدام الضرب المدرسي، أو حل مشكلة الرنية يأخذ $ O (NT) $ < / span >- الوقت حيث $ n $ هو عدد العناصر و $ T $ هو المبلغ المستهدف .

في حالات خاصة مثل الرسوم البيانية المستوية والرسوم البيانية الأخرى المتناثرة، نحن نعرف أن $ m= o (n) $ ، حتى نتمكن من استبدال $ n $ بدلا من $ m $ في وقت التشغيل النهائي للبسط.

كأنقطة، وهذا يوضح السبب في الرسوم البيانية المتناثرة (حيث $ m= o (n) $ ) يفضل المرء استخدام dijktra في حلقة لكل حلقة أزواج أقصر مسار (على عكس خوارزمية تعتمد على الإغلاق متعدية مثل Floyd-Warshall)؛ منذ الآن Dijkstra يعمل في $ o (m \ log n)= o (n \ log n) $ ، أصبح التعقيد العام لاستخدام dijkstra في حلقة $ O (n ^ 2 \ Log n) $ ، وهو أفضل من Floyd-Warshall. على النقيض من ذلك، لاحظ أن Dijkstra يعمل في $ m \ log n $ للحصول على الحالة العامة، مما يعني على الرسوم البيانية الكثيفة حيث $ M= O (n ^ 2) $ ، يصبح أقل كفاءة من floyd-warshall من حيث وقت التشغيل الأسوأ.

في حالات أخرى، يمكن أن تكون هناك متغيرات لا تحد متعدد الحدود من خلال معلمة معينة --- تأخذ مثال الحرف أعلاه، حيث يمكن أن يكون $ t $ يمكن أن يكون الأسي في $ n $ .

Answer 2

لا يوجد إجابة عامة.بالمناسبة، إذا كنت ترغب في تبسيط $ o (\ max (n \ log (n)، m \ log (m))) $ ، يمكنك إعادة كتابةكما as $ O ((n + m) \ log (n + m)) $ .

علاوة على ذلك، إذا كان $ g_1 $ و $ g_2 $ هي وظائف eqaul وزيادة، يمكنك الكتابة $ O (g_1 (n + m)) $ بدلا من $ o (\ max (g_1 (n)، g_2 (م))) $ .

Answer 3

بحكم تعريف $ o (g) $ يجب أن تكون دائما محددة متغير ومتغير نقطة مع الاحترام هو تفكير $ o $ . على سبيل المثال في $ o (n ^ 3)، n \ to \ isty $ المتغير هو $ n $ وحد نقطة $ \ infty $ . في $ o (x ^ 3)، x \ to 0 $ المتغير هو $ x $ ونقطة الحد $ 0 $ .

لذلك عندما نكتب $ f= o (g) $ ، ثم نعني رسميا بعض المتغير ونقطة الحد. على سبيل المثال $ f (n)= o (g (n))، n \ to \ enfty $ هو سجل دقيق. ملاحظة، أن تسجيل $ f (m)= o (g (m))، m \ to \ enfty $ يعني تماما نفس الجملة السابقة.

عندما نتحدث عن الممتلكات $ f_1 + f_2= o (\ max (g_1، g_2)) $ ، ثم يجب أيضا ذكر بعض المتغير (S) ) وبعض نقاط الحد. يجب أن يكون السجل بالضبط شيء مثل $$ f_1 (n) + f_2 (n)= o (\ max (g_1، g_2) (n))، n \ to \ enfty $$ أو نحتاج إلى مزيد من التوضيح فيما يتعلق بالمتغيرات، وتحمل نقطة الحد $ \ infty $ .