{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Landau-Symbole"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\Theta(g)$ ist die Menge aller Funktionen, die genauso schnell wachsen wie g. Formal:\n",
"\n",
"$$\\Theta(g) = \\{f\\mid{} \\exists c>0,\\exists c'> 0,\\exists n_0> 0 \\text{, so dass } \\forall\n",
" n \\geq n_0: c\\cdot g(n)\\leq f(n) \\leq c'\\cdot g(n)\\}$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Bei der Analyse interessiert nur der Term höchster Ordnung (= am schnellsten wachsender Summand) einer Funktion.\n",
"\n",
"Plotten wir zunächst einmal einige wichtige Funktionen, um einen Eindruck zu bekommen wie schnell sie wachsen (v.a. auch im Verhältnis zu den anderen Funktionen)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%matplotlib inline\n",
"\n",
"import matplotlib\n",
"import matplotlib.pyplot as plt\n",
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x = np.linspace(0.01, 10, 500)\n",
"\n",
"plt.plot(x, np.log2(x), label=r'$\\log_2(x)$')\n",
"plt.plot(x, x, label=r'$x$')\n",
"plt.plot(x, x*np.log2(x), label=r'$x\\log_2(x)$')\n",
"\n",
"plt.plot(x, x**2, label=r'$x^2$')\n",
"plt.plot(x, x**3, label=r'$x^3$')\n",
"plt.plot(x, 2**x, label=r'$2^x$')\n",
"\n",
"legend = plt.legend()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Theta"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Betrachten wir $f(x) = 2x^3 - 3x^2 + 100x\\log_2(x) + 50000$ und $g(x) = x^3$. Wir wollen zeigen, dass $f \\in \\Theta(g)$ (also $f\\in\\Theta(x^3)$).\n",
"\n",
"*Aufgabe:* Finden Sie Werte für `c1`, `c2` und `n0`, so dass für alle $x\\geq{}$ `n0` gilt, dass `c1`${}\\cdot x^3 \\leq f(x) \\leq{}$ `c2` ${}\\cdot x^3$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"xrange = 50 # Hier können Sie einstellen, wie weit die x-Achse dargestellt wird\n",
"x = np.linspace(0.01, xrange, 500)\n",
"plt.plot(x, 2*x**3 - 3*x**2 + 100*x*np.log2(x) + 50000, label=r'$2x^3 - 3x^2 + 100x\\log_2(x) + 50000$')\n",
"#plt.plot(x, x**3, label=r'$x^3$')\n",
"\n",
"c1 = 0 # TODO\n",
"c2 = 0 # TODO\n",
"n0 = 0 # TODO\n",
"plt.plot(x, c1*x**3, label=r'$%sx^3$' % c1)\n",
"plt.plot(x, c2*x**3, label=r'$%sx^3$' % c2)\n",
"plt.axvline(x=n0)\n",
"legend = plt.legend()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*Aufgabe:* Gilt auch $f\\in \\Theta(x^2)$?\n",
"\n",
"Suchen Sie wieder entsprechende Werte für `c1`, `c2` und `n0`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"xrange = 50 # Hier können Sie einstellen, wie weit die x-Achse dargestellt wird.\n",
"x = np.linspace(0.01, xrange, 500)\n",
"plt.plot(x, 2*x**3 - 3*x**2 + 100*x*np.log2(x) + 50000, label=r'$2x^3 - 3x^2 + 100x\\log_2(x) + 50000$')\n",
"\n",
"c1 = 0 # TODO\n",
"c2 = 0 # TODO\n",
"n0 = 0 # TODO\n",
"plt.plot(x, c1*x**2, label=r'$%sx^2$' % c1)\n",
"plt.plot(x, c2*x**2, label=r'$%sx^2$' % c2)\n",
"plt.axvline(x=n0)\n",
"legend = plt.legend()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.7"
}
},
"nbformat": 4,
"nbformat_minor": 2
}