Complexity, Landau Notation

Question 1

Definition von 𝛺

Formel?

Answer 1

Definition:

𝛺(𝑔) = {𝑓: ℕ → ℝ_(>=0 )| ∃ 𝑐, 𝑛0 > 0 ∀ 𝑛 ≥ 𝑛0: 𝑓(𝑛) ≥ 𝑐 * 𝑔(𝑛)}

Question 2

Definition von 𝛺

Beschreibung

Answer 2

Wir schreiben 𝑓(𝑛) ∈ 𝛺(𝑔) , falls 𝑔 eine untere Schranke von 𝑓 ist, d.h., 𝑓 wächst asymptotisch mindestens so schnell wie 𝑔.

Question 3

Definition von 𝛺

Beispiele

Answer 3

Beispiele:
* n^2 ∈ Ω(sqrt(n)),
* n^2 ∈ Ω(n^2),
* n^2 ∉ Ω(n^3)

Question 4

Definition von O

Formel

Answer 4

Ο(𝑔) = {𝑓: ℕ → ℝ_(>=0 ) | ∃𝑐 > 0 ∃ 𝑛0 ≥ 0 ∀𝑛 ≥ 𝑛0: 𝑓(𝑛) ≤ 𝑐 * 𝑔(𝑛)}

Wir definieren eine Menge 𝑂(𝑔),

sie besteht aus der Menge aller Funktionen f

Es existieren zwei Konstanten c und n_0,

Die nachfolgende Aussage gilt ab einer Konstanten n0, 𝑐 * 𝑔(𝑛) ist obere Schranke für f(𝑛)

Question 5

Definition von O

Text

Answer 5

Wir schreiben f(n) ∈ O(g), falls g eine obere Schranke von f ist, d.h., f wächst asymptotisch höchstens so schnell wie g.

Question 6

Definition von O

Beispiele

Answer 6

Beispiele:
* 10 * n^2+n ∈ O(n^2),
* 10 * n^2 ∈ O(n^3),
* n2 ∉ O(n)

Question 7

Definition von Θ

Formel

Answer 7

Θ(g) = {𝑓: ℕ → ℝ_(>=0 )| ∃ 𝑐_1, c_2, 𝑛_0 > 0 ∀𝑛 ≥ 𝑛0 : 𝑐_1𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐_2𝑔(𝑛)}

Question 8

Definition von Θ

Text

Answer 8

Wir schreiben f(n) ∈ Θ(g), falls g untere und obere
Schranke von f ist, d.h., f wächst asymptotisch ebenso
schnell wie.

Question 9

Definition von Θ

Beispiele

Answer 9

n^2 + n ∈ Θ(n^2)

Question 10

Definition von o(g)

„f“ wächst asymptotisch wesentlich _______________als „g“ ?

Answer 10

o(𝑔) = {𝑓| ∀𝑐 > 0 ∃ 𝑛0 > 0 ∀𝑛 ≥ 𝑛0: 𝑓(𝑛) < 𝑐 * 𝑔(𝑛)}

„f“ wächst asymptotisch wesentlich langsamer als „g“

Question 11

Definition von ω(g)

„f“ wächst asymptotisch wesentlich _______________als „g“ ?

Answer 11

ω(𝑔) = {𝑓| ∀𝑐 > 0 ∃ 𝑛0 > 0 ∀𝑛 ≥ 𝑛0: 𝑓(𝑛) > 𝑐 * 𝑔(𝑛)}

„f“ wächst asymptotisch wesentlich schneller als „g“

Question 12

Allgemein: Konstante Funktionen wachsen asymptotisch ______ ______

Answer 12

Allgemein: Konstante Funktionen wachsen asymptotisch gleich schnell

Question 13

Satz:

limit n → ∞ ( f(n) / g(n) ) = 0

–> f ∈ ??

Answer 13

f ∈ o(g)

Question 14

Satz:

limit n → ∞ ( f(n) / g(n) ) = ∞

–> f ∈ ??

Answer 14

ω(𝑔)

Question 15

Satz:

limit n → ∞ ( f(n) / g(n) ) < ∞

–> f ∈ ??

Answer 15

O(g)

Question 16

Satz:

limit n → ∞ ( f(n) / g(n) ) > 0

–> f ∈ ??

Answer 16

𝛺(𝑔)

Question 17

Satz:

limit n → ∞ ( f(n) / g(n) ) = c ∈ ℝ
–> f ∈ ??

Answer 17

Θ(g)

Question 18

Satz von L’Hopital

Answer 18

Für zwei differenzierbare Funktionen f und g mit

limit n → ∞ f(n) = limit n → ∞ g(n) = 0 oder
limit n → ∞ f(n) = limit n → ∞ g(n) = ∞

gilt:

limit n → ∞ ( f(n) / g(n) ) = (L’H) limit n → ∞ ( f’(n) / g’(n) )

Question 19

Nützliche Zusammenhänge:

f ∈ O(g) ⟺ g ∈ ?

Answer 19

Ω(f)

Question 20

Nützliche Zusammenhänge:

f ∈ o(g) ⟺ g ∈ ?

Answer 20

ω(g)

Question 21

Nützliche Zusammenhänge:

f ∈ o(g) ⟺ f ∈ ?

Answer 21

O(g)

Question 22

Nützliche Zusammenhänge:

f ∈ o(g) ⟺ f ∉ ?

Answer 22

Ω(g)

Question 23

Nützliche Zusammenhänge:

f ∈ ω(g) ⟺ f ∈ ?

Answer 23

Ω(g)

Question 24

Nützliche Zusammenhänge:

f ∈ ω(g) ⟺ f ∉ ?

Answer 24

O(g)

Question 25

Logarithmengesetze:
log2(n)’ = ?

Answer 25

log2(n)’ = (ln n / ln 2)’ = 1 / (ln 2 * n)