كبير-أوه ، Concequence تعريف

Question

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

حتى هنا هو التعريف الذي أعطيت في الملاحظات:

و السؤال لقد أعطيت هو:

باستخدام تعريف 2.5 تظهر أنه إذا كان f(n) O(g(n)) ثم k + f(n) هو أيضا O(g(n)).

لقد قضيت 3 أيام من البحث في الإنترنت عن أي نوع من الإجابة على مثل هذه المشاكل.تبحث في تعريف 2.5 تقول f(n) O(g(ن)) و k + f(n) O(g(n)).هذا يكفي بالنسبة لي ، ولكن يبدو أنه يجب أن يثبت كيف أن مشتق.اعتقدت في البداية أنه يجب أن يتم ذلك بطريقة أو بأخرى من خلال إستقراء ولكن منذ ذلك الحين قررت ضد هذا و يجب أن يكون هناك طريقة أسهل.

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

شكرا مقدما.

Answer 1

لنفترض f(n) O(g(n))
ثم هناك وجود c و k' s.t.لكل ن > k':f(n) <= cg(n)
الآن النظر في f(n) + k
د أن ق.t k <= d*g(n) من أجل كل n أكبر من ك
التي تعرف ممكن لأن ك في س(1)
ثم
f(n) + k <= cg(n) + dg(ن) = (d+c)(g(n))
ثم يمكنك استخدام تعريف بديل d+c c ==> f+k في O(g)

Answer 2

f(n) <= cg(n)

k + f(n) <= ج'g(n) حيث c' = ck

لذا k + f(n) O(g(n))

Answer 3

ثم k هو O(1), f(n) هو O(g(n)) ثم يمكنك أن مجموع هذه القيم ثم لديك O(1+g(n)) هذا هو O(g(n));

f(n) هو O(g(n)) ثم k + f(n) هو أيضا O(g(n)), لأن لديك وريتيد في كتابك

تجاهل إضافة المستمر

ثابت دائما يتم تجاهل لأنه لا يمكن تغيير Big-O تدوين أي ثابت O(1) في Big-O التدوين.

Answer 4

ما يستحق, هذا هو إلى حد ما المفتعلة تعريف big-O التدوين.أكثر العامة و في رأيي أكثر سهولة تعريف f(n) ~ O(g(n)) كما n->a المنتدى lim|f(n)/g(n)| <= A كما n->a لبعض محدودة العدد الحقيقي A.

الجزء المهم هو أن حد السياق هو مطلوب.في CS, أن الحد مأخوذ ضمنا إلى ما لا نهاية (لأن هذا هو ما n يميل إلى مشكلة حجم الزيادات) ، ولكن من حيث المبدأ يمكن أن يكون أي شيء.على سبيل المثال ، sin(x) ~ O(x) كما x->0 (في الواقع, انها بالضبط مقارب إلى x;هذا هو زاوية صغيرة التقريب).