What the Big Theta allows us to do is basically write complicated functions
in a much simpler way.
We can take a function like ½n² and just think of it as Θ(n²).
And 8√n we can think of a just Θ(√n).
Our equation from before, 2n - 2√n just becomes Θ(n).
It's just a linear function asymptotically.
A complicated expression like this where we have n⁴, which is the term that grows the fastest,
becomes Θ(n).
The ln n--in fact, any base log n is Big Theta of any other base log n as long as it's a constant.
I like to think in terms of base 2 logs, because I'm a computer scientist.
That's what we do.
π² is something that doesn't grow with n, and it ends up being in the set Θ(1).
It's just another constant.
Just to beat this dead horse a little bit longer, let's use the definition of Big Theta
to show that this expression that we determine for the growth in edges in a grid--
2n - 2√n--really is just a linear function. It grows like Θ(n).
The game plan is that we need to find constant c₁ and c₂--bigger than 0
and a threshold N₀ so that for all the n bigger than n₀, the function that we care about
is sandwiched between these two scalings.
Let's focus on this one first.
What c₂ can we plug in here so that we're guaranteed that this will be above this expression.
If we just copy this inequality down just flipping it around to make it a little easier to think about,
we want c₂ so that c₂n is bigger than this. Divide through by n
Now we need a c₂ that is bigger than 2 minus something that's actually growing.
Two should work for that.
If we set c₂ to 2, it will satisfy this inequality.
Let's just summarize all that
We can set c₂ = 2. What about c₁?
Well, let's take c₁ to be 1.
Intuitively, the idea being this function is growing like 2n minus something smaller than that.
So, n should be underneath that.
But let's just make show if c₁ is equal to 1, then we need n to be less than or equal
to this expression. For what values of n is that going to be true?
It's not true of all of them, but it's true for some of them.
We can add 2√n to both sides, subtract n from both sides, and we get that.
If we divide through by √n, we get 2 ≤ n/√n and divided by √n is actually √n.
So, we have 2 ≤ √n.
We square both sides. We have 4 ≤ n, or--flipping that around the other way--
if n ≥ 4, then this is true
That means we have to throw away the smaller values of n,
and we can do that very simply by setting n₀ to 4.
This only has to hold for n that are bigger than n₀.
That's what we've got there.
There we have it.
If we set the constants this way, n₀, c₁, and c₂, then what we find is
that for big enough n this more complicated expression is sandwiched between
two simple linear functions or to say it another way--
क्या बड़ा थीटा करने के लिए हमें की अनुमति देता है मूल रूप से जटिल कार्य लिखें
एक बहुत आसान तरीका में।
हम ½n² की तरह एक कार्य ले और बस लगता है कि यह के रूप में Θ(n²) कर सकते हैं।
और हम एक ही Θ(√n) के लगता है कि कर सकते हैं 8√n.
से हमारे समीकरण से पहले, 2n - 2√n सिर्फ Θ(n) हो जाता है।
यह सिर्फ एक रैखिक समारोह निवेश है।
इस तरह एक जटिल अभिव्यक्ति जहाँ हम n⁴, जो कि सबसे तेजी से बढ़ता है शब्द है, है
Θ(n) हो जाता है।
के रूप में लंबे समय के रूप में यह एक स्थिरांक है ln एन - वास्तव में, किसी भी आधार लॉग n किसी भी अन्य आधार लॉग n के बड़े थीटा है।
क्योंकि मैं एक कंप्यूटर वैज्ञानिक मैं आधार 2 लॉग के मामले में, लगता है कि करने के लिए पसंद है।
कि हमें क्या करना है।
Π² कुछ है कि n के साथ हो जाना नहीं करता है, और यह अंत में सेट Θ(1) जा रही है।
यह सिर्फ एक और निरंतर है।
बस एक छोटा सा अब इस मरे हुए घोड़े को हरा करने के लिए, चलो बड़ा थीटा की परिभाषा का उपयोग करें
पता चलता है कि इस अभिव्यक्ति है कि हम एक ग्रिड में किनारों में विकास के लिए यह निर्धारित करने के लिए-
2n - 2√n - सच में सिर्फ एक रैखिक समारोह है। यह Θ(n) की तरह होती है।
खेल की योजना है कि हम निरंतर c₁ और c₂ - 0 से बड़ा को खोजने के लिए की जरूरत है
और एक सीमा से N₀ इतना है कि सभी एन n₀, इस समारोह कि हम के बारे में ध्यान से बड़ा के लिए
इन दो scalings के बीच sandwiched है।
चलो यह एक पर पहले ध्यान केंद्रित।
इतना है कि हम गारंटी कर रहे हैं कि इस के ऊपर इस अभिव्यक्ति हो जाएगा क्या c₂ हम यहाँ कर सकते हैं में प्लग।
अगर हम सिर्फ चारों ओर बस के बारे में सोचने के लिए थोड़ा आसान बनाने के लिए flipping नीचे इस असमानता की प्रतिलिपि बनाएँ,
हम c₂ चाहते हैं ताकि c₂n इस से बड़ा है। के माध्यम से एन द्वारा फूट डालो
अब हम जो वास्तव में बढ़ रहा है कि कुछ है शून्य से 2 से बड़ा है एक c₂ की जरूरत है।
दो इसके लिए काम करना चाहिए।
अगर हम 2 करने के लिए c₂ सेट करें, यह इस असमानता को संतुष्ट करेगा।
चलो बस सभी कि संक्षिप्त
हम c₂ सेट कर सकते हैं = 2। C₁ के बारे में क्या?
ठीक है, चलो c₁ 1 होना करने के लिए ले लो।
Intuitively, विचार किया जा रहा यह फ़ंक्शन शून्य से कुछ है कि अधिक छोटे 2n की तरह बढ़ रहा है।
तो, एन कि नीचे होना चाहिए।
लेकिन हम बस कर यदि c₁ 1 के बराबर है, तो हम एन से कम या बराबर होना करने के लिए की जरूरत है दिखाएँ
इस अभिव्यक्ति के लिए। क्या एन के मूल्यों के लिए सच हो करने के लिए चल रहा है?
यह सब के सब के सच नहीं है, लेकिन यह उन में से कुछ के लिए सच है।
हम दोनों पक्षों को 2√n जोड़ने के लिए, दोनों तरफ से n घटाना कर सकते हैं, और है कि हम मिल।
अगर हम ने √n के माध्यम से विभाजित है, हम 2 ≤ n/√n और √n द्वारा विभाजित किया वास्तव में √n है।
तो, हम 2 ≤ √n है।
हम दोनों ओर वर्ग। हम 4 ≤ n, या - कि flipping अन्य रास्ते - भर है
यदि n ≥ 4, तो यह सच है
इसका मतलब है कि हम छोटे मूल्यों के n फेंक करने के लिए है,
और हम कर सकते हैं कि बस बहुत n₀ करने के लिए 4 सेट करके।
यह केवल कि n₀ से भी बड़ा रहे हैं n के लिए रोक दिया।
यह है कि क्या हम वहाँ मिल गया है।
वहाँ हम इसे है।
अगर हम इस तरह से स्थायी सेट, n₀, c₁, और c₂, तो क्या हम पाते है
कि बहुत बड़ा n के लिए यह अधिक अभिव्यक्ति जटिल के बीच sandwiched है
दो सरल रैखिक कार्य या यह एक और तरीका है - कहने के लिए
ビッグ・シータを使うと
複雑な関数を簡潔に書き表すことができます
1/2(n²)という関数ならΘ(n²)で考え
8√nならΘ(√n)で考えられます
前に出てきた2n-2√nという式ならΘ(n)です
これは漸近的には線形関数です
一方このn⁴を含んだ複雑な式は
非常に速く成長しますがΘ(n⁴)と表せます
nの自然対数 ただし実際にはどの底のlog nでも
底が定数であるならΘ(log n)です
私はコンピュータ科学者なので
底が2の対数で考えることが多いですね
π²はnと共に成長せず
最後には集合Θ(1)の要素となります
これも単なる定数です
もう少しだけビッグ・シータの定義を使って
格子グラフのエッジの数を計算する2n-2√nが
Θ(n)のように成長する線形関数であることを
示したいと思います
そのためにはゼロより大きな定数c₁、c₂と
閾値n₀を見つける必要がありますが
その時n₀より大きなすべてのnで
この関数はこの2つのスケーリングの間にあります
まずこちらを見ましょう
c₂が入っている理由は
この式より確実に大きくするためです
分かりやすいように
この不等式を反対に書いてみると
c₂nの方が大きいのでこうなります
そしてnで割ります
するとc₂の値は
2からこの増加する値を引いたもの以上となります
2ならうまくいくはずです
c₂を2とするとこの式を満たします
以上の内容をまとめると
c₂=2と設定できます
ではc₁は1としましょう
この関数の成長率は
2nから2n未満の値を引いたものです
するとnはそれ以下になります
もしc₁が1なら
nはこの式の値以下である必要があります
それを満たすnの値は?
いくつかの値は当てはまります
両辺において2√nを足してnを引きます
さらに√nで割ると2≦n/√nとなり
この値は√nとなります
すると2≦√nです
両辺を2乗すると4≦nとなります 逆向きにすると
もしn≧4ならこれが成り立ちます
つまりnの小さな値を捨てる必要がありますが
n₀を4とすればそれが可能です
これが当てはまるのはnがn₀より大きい場合のみです
これですべてを示すことができました
定数であるn₀、c₁、c₂をこのように設定すると
十分に大きなnにおいてこの複雑な式は
2つの簡単な線形関数の間にある つまりこれですね