Hindi 字幕

← 02-12 Big-Theta Examples

埋め込みコードを取得する
3言語

Showing Revision 1 created 03/23/2013 by Nirmal Khatua.

  1. क्या बड़ा थीटा करने के लिए हमें की अनुमति देता है मूल रूप से जटिल कार्य लिखें
  2. एक बहुत आसान तरीका में।
  3. हम ½n² की तरह एक कार्य ले और बस लगता है कि यह के रूप में Θ(n²) कर सकते हैं।
  4. और हम एक ही Θ(√n) के लगता है कि कर सकते हैं 8√n.
  5. से हमारे समीकरण से पहले, 2n - 2√n सिर्फ Θ(n) हो जाता है।
  6. यह सिर्फ एक रैखिक समारोह निवेश है।
  7. इस तरह एक जटिल अभिव्यक्ति जहाँ हम n⁴, जो कि सबसे तेजी से बढ़ता है शब्द है, है
  8. Θ(n) हो जाता है।
  9. के रूप में लंबे समय के रूप में यह एक स्थिरांक है ln एन - वास्तव में, किसी भी आधार लॉग n किसी भी अन्य आधार लॉग n के बड़े थीटा है।
  10. क्योंकि मैं एक कंप्यूटर वैज्ञानिक मैं आधार 2 लॉग के मामले में, लगता है कि करने के लिए पसंद है।
  11. कि हमें क्या करना है।
  12. Π² कुछ है कि n के साथ हो जाना नहीं करता है, और यह अंत में सेट Θ(1) जा रही है।
  13. यह सिर्फ एक और निरंतर है।
  14. बस एक छोटा सा अब इस मरे हुए घोड़े को हरा करने के लिए, चलो बड़ा थीटा की परिभाषा का उपयोग करें
  15. पता चलता है कि इस अभिव्यक्ति है कि हम एक ग्रिड में किनारों में विकास के लिए यह निर्धारित करने के लिए-
  16. 2n - 2√n - सच में सिर्फ एक रैखिक समारोह है। यह Θ(n) की तरह होती है।
  17. खेल की योजना है कि हम निरंतर c₁ और c₂ - 0 से बड़ा को खोजने के लिए की जरूरत है
  18. और एक सीमा से N₀ इतना है कि सभी एन n₀, इस समारोह कि हम के बारे में ध्यान से बड़ा के लिए
  19. इन दो scalings के बीच sandwiched है।
  20. चलो यह एक पर पहले ध्यान केंद्रित।
  21. इतना है कि हम गारंटी कर रहे हैं कि इस के ऊपर इस अभिव्यक्ति हो जाएगा क्या c₂ हम यहाँ कर सकते हैं में प्लग।
  22. अगर हम सिर्फ चारों ओर बस के बारे में सोचने के लिए थोड़ा आसान बनाने के लिए flipping नीचे इस असमानता की प्रतिलिपि बनाएँ,
  23. हम c₂ चाहते हैं ताकि c₂n इस से बड़ा है। के माध्यम से एन द्वारा फूट डालो
  24. अब हम जो वास्तव में बढ़ रहा है कि कुछ है शून्य से 2 से बड़ा है एक c₂ की जरूरत है।
  25. दो इसके लिए काम करना चाहिए।
  26. अगर हम 2 करने के लिए c₂ सेट करें, यह इस असमानता को संतुष्ट करेगा।
  27. चलो बस सभी कि संक्षिप्त
  28. हम c₂ सेट कर सकते हैं = 2। C₁ के बारे में क्या?
  29. ठीक है, चलो c₁ 1 होना करने के लिए ले लो।
  30. Intuitively, विचार किया जा रहा यह फ़ंक्शन शून्य से कुछ है कि अधिक छोटे 2n की तरह बढ़ रहा है।
  31. तो, एन कि नीचे होना चाहिए।
  32. लेकिन हम बस कर यदि c₁ 1 के बराबर है, तो हम एन से कम या बराबर होना करने के लिए की जरूरत है दिखाएँ
  33. इस अभिव्यक्ति के लिए। क्या एन के मूल्यों के लिए सच हो करने के लिए चल रहा है?
  34. यह सब के सब के सच नहीं है, लेकिन यह उन में से कुछ के लिए सच है।
  35. हम दोनों पक्षों को 2√n जोड़ने के लिए, दोनों तरफ से n घटाना कर सकते हैं, और है कि हम मिल।
  36. अगर हम ने √n के माध्यम से विभाजित है, हम 2 ≤ n/√n और √n द्वारा विभाजित किया वास्तव में √n है।
  37. तो, हम 2 ≤ √n है।
  38. हम दोनों ओर वर्ग। हम 4 ≤ n, या - कि flipping अन्य रास्ते - भर है
  39. यदि n ≥ 4, तो यह सच है
  40. इसका मतलब है कि हम छोटे मूल्यों के n फेंक करने के लिए है,
  41. और हम कर सकते हैं कि बस बहुत n₀ करने के लिए 4 सेट करके।
  42. यह केवल कि n₀ से भी बड़ा रहे हैं n के लिए रोक दिया।
  43. यह है कि क्या हम वहाँ मिल गया है।
  44. वहाँ हम इसे है।
  45. अगर हम इस तरह से स्थायी सेट, n₀, c₁, और c₂, तो क्या हम पाते है
  46. कि बहुत बड़ा n के लिए यह अधिक अभिव्यक्ति जटिल के बीच sandwiched है
  47. दो सरल रैखिक कार्य या यह एक और तरीका है - कहने के लिए