%Teilweise Erzeugt mit dem LaTeX-Generator: http://latex.sehnot.de

%Schriftgröße, Layout, Papierformat, Art des Dokumentes
\documentclass[10pt,oneside,a4paper]{scrartcl}

%Einstellungen der Seitenränder
\usepackage[left=2cm,right=2cm,top=1.5cm,bottom=1.5cm,includeheadfoot]{geometry}

%neue Rechtschreibung
\usepackage[ngerman]{babel}

%Umlaute ermöglichen
\usepackage[utf8]{inputenc}

%Gesamtseitenzahl
\usepackage{lastpage}

% Kopf- und Fußzeile
\usepackage[automark]{scrpage2}

%Quellcode-Listings
\usepackage{listings}

%Hyperlinks
\usepackage{hyperref}

%Bilder
\usepackage{graphicx}
\usepackage{graphics}

\usepackage{setspace}
\usepackage{multicol}

% Schriftarten für fettes Monospace
%\usepackage[T1]{fontenc}
%\usepackage{lmodern}

% Symbol für natürliche Zahlen
\usepackage{amssymb} 

%Kopfzeile
\ihead{Informatik}
\chead{}
\ohead{http://kohnlehome.de/informatik/big-o-algorithmen.pdf}
\setheadsepline{0.5pt}

%Fußzeile
\setfootsepline{0.5pt}
\ifoot{\href{http://kohnlehome.de/}{Franz Kohnle}}
\cfoot{Seite \thepage\ von  \pageref{LastPage}}
\ofoot{\today}

\pagestyle{scrheadings}

\begin{document}

% Überschrift 
\begin{center}
\LARGE % Schriftgröße
\bfseries % Fettdruck
\sffamily % Serifenlose Schrift
Komplexität von Algorithmen
\end{center}

\section*{Big-O-Notation (asymptotische obere Schranke)}
$f(n) \, ist \, von \, \mathcal{O}(g(n)) \, genau \, dann,
wenn \, n_{0} \in \mathbb{N}  \, und \, c \in \mathbb{R}+ existieren \, mit \, f(n) \leq c \cdot g(n) f\ddot{u}r \, alle \, n \leq n_{0}$.

\section*{Beispiele}
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{c | c | l}
Komplexität & Bedeutung & Algorithmus \\ \hline \hline

$\mathcal{O}(1)$ & konstant & Element aus einem Array holen\\ \hline

$\mathcal{O}( log \, n)$ & logarithmisch & Binäre Suche\\ \hline

$\mathcal{O}(\sqrt{n})$ & wie Wurzel & Naiver Primzahltest\\ \hline

$\mathcal{O}(n)$ & linear & Lineare Suche\\ \hline

$\mathcal{O}(n \, log \, n)$ & superlinear & Mergesort, Heapsort\\ \hline

$\mathcal{O}(n^{2})$ & quadratisch & Selectionsort\\ \hline

$\mathcal{O}(n^{m})$ & polynomiell & Einfache Algorithmen\\ \hline\hline

$\mathcal{O}(2^{n})$ & exponentiell & \\ \hline

$\mathcal{O}(n!)$ & faktoriell & Problem des Handlungsreisenden\\ \hline


\end{tabular}

\end{document}

