complexity-nl.tex

\documentclass[12pt]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[frenchb]{babel}
\usepackage{listings}
\usepackage{tabu}
\usepackage{color}
\usepackage{booktabs}
\beamertemplatenavigationsymbolsempty
\AtBeginSection[]
{
    \begin{frame}
    \frametitle{Inhoudstafel}
    \tableofcontents[currentsection]
    \end{frame}
}
\lstset{language=C++, basicstyle=\footnotesize, frame=single}
\newcommand{\gray}{\textcolor{gray}}

\title{Algoritmes en complexiteit}
\subtitle{Definities en grote-O-notatie}
\author{beOI Training}
\institute{\includegraphics[height=12em]{../share/beoi-logo}}

\begin{document}

\frame{\titlepage}

\section{Algoritmes}

\begin{frame}
\frametitle{Wat is een algoritme?}
\begin{itemize}
\item Een manier om een resultaat te berekenen
\item Een idee om een probleem op te lossen
\item Een opeenvolging van instructies
\item De beschrijving van een programma
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Wat is een \emph{goed} algoritme?}
Aandachtspunten voor de programmeur
\begin{itemize}
\item Crasht niet
\item Eindigt
\item Geeft het goede antwoord
\end{itemize}

~

Aandachtspunten voor de competitieve programmeur
\begin{itemize}
\item Snelheid
\item Weinig geheugengebruik
\item \textbf{Wordt geaccepteerd in een wedstrijd}
\end{itemize}
\end{frame}

\section{Complexiteit}

\begin{frame}
\frametitle{De efficiëntie meten}
Ideëen
\begin{itemize}
\item De tijd opmeten
\item Het RAM geheugen dat gebruikt wordt opmeten
\end{itemize}

~

Maar varieert volgens
\begin{itemize}
\item Taal
\item Implementatie
\item Machine
\item Uur van de dag
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{grote-O-notatie}
Geeft een \emph{intrinsieke} notie van efficiëntie weer:
\begin{itemize}
\item Door de input te vergroten
\item Door te kijken hoe de snelheid evolueert
\end{itemize}

~

Voorbeeld: bereken $1+\cdots+n$.Als $n$ vermenigvuldigd wordt met 2, dan zou het volgende kunnen gebeuren met de tijd:
\begin{itemize}
\item Blijft constant: $O(1)$
\item Wordt vermenigvuldigd met 2: $O(n)$
\item Wordt vermenigvuldigd met 4: $O(n^2)$
\end{itemize}

~

Dit is onafhankelijk van constante factoren!
\end{frame}

\begin{frame}[fragile]
\frametitle{Constante tijd}
\textbf{Probleem:} Bereken de som: $1+2+\cdots+n$.

~

\textbf{Oplossing 1:} Een simpele berekening
\begin{lstlisting}
int sum = n * (n+1) / 2;
\end{lstlisting}
\begin{itemize}
\item Tijd verandert niet als $n$ verdubbelt
\item "constante" tijd
\item  $O(1)$ complexiteit
\item Een tijd ``proportioneel met $1$''
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Lineaire tijd}
\textbf{Oplossing 2:} Een lus
\begin{lstlisting}
int sum = 0;
for (int i = 1; i <= n; i++)
    sum += i;
\end{lstlisting}
\begin{itemize}
\item Tijd verdubbelt als $n$ verdubbelt
\item ``lineaire'' tijd
\item  $O(n)$ complexiteit
\item Een tijd ``proportioneel met $n$''
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Kwadratische tijd}
\textbf{Oplossing 3:} Twee lussen (dom!)
\begin{lstlisting}
int sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        sum++;
\end{lstlisting}
\begin{itemize}
\item Tijd wordt vier keer groter als $n$ verdubbelt
\item ``Kwadratische'' tijd
\item  $O(n^2)$ complexiteit
\item Een tijd ``proportioneel met $n^2$''
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Machten}
Definitie:
\begin{itemize}
\item Herhaald vermenigvuldigen
\item ``3 tot de macht $n$''
\item $3^n = \underbrace{3\times\cdots\times3}_\text{$n$ keer}$
\end{itemize}
Voorbeelden:
\begin{itemize}
\item $3^0 = 1$ (dit is zo gedefinieerd)
\item $3^1 = 3$
\item $3^2 = 3 \times 3 = 9$ (kwadraat)
\item $3^3 = 3 \times 3 \times 3 = 27$ (derde macht)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Logaritmes: intuïtie (1)}
Spel met twee spelers:
\begin{itemize}
\item Alice kiest een getal tussen 1 en 16
\item Om de beurt gebeurt het volgende:
    \begin{itemize}
    \item Bob geeft Alice één of meerdere getallen
    \item Alice zegt of haar getal tussen die getallen zit
    \end{itemize}
\item Wanneer Bob het getal gevonden heeft, wint hij
\item Hoe kan hij winnen in zo weinig mogelijk zetten?
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Logaritmes: intuïtie (2)}
\textbf{Strategie:} Geef de helft van de mogelijke getallen
\begin{itemize}
\item Eerst 8 getallen uit 16
\item Vervolgens 4 getallen uit de overgebleven 8
\item Vervolgens 2 getallen uit de overgebleven 4
\item Vervolgens 1 getal uit de overgebleven 2
\item Gevonden!
\end{itemize}

~

Dus 4 vragen zijn voldoende.
\end{frame}

\begin{frame}
\frametitle{Logaritmes: intuïtie (3)}
In het algemeen, als we starten met $n$ getallen, hoeveel vragen zijn er dan nodig?

~

Hoe vaak kan je in 2 helften splitsen?
\begin{itemize}
\item Als $n=2$, één keer
\item Als $n=4$, twee keer
\item Als $n=8$, drie keer
\item Als $n=16$, vier keer
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Basis 2 logaritme}
De functie die het antwoord biedt op deze vraag is $\log_2$: De basis 2 logaritme. Bijvoorbeeld
\begin{itemize}
\item $\log_2 (2) = 1$
\item $\log_2 (4) = 2$
\item $\log_2 (8) = 3$
\item $\log_2 (16) = 4$
\end{itemize}
De strategie van Bob is $O(\log_2(n)) = O(\log n)$.

~

De basis 2 logaritme is dus de macht waartoe je 2 moet verheffen om $n$ te krijgen:
\[ x = \log_2 (n)\ \Leftrightarrow\ 2^x = n \]
\end{frame}

\begin{frame}
\frametitle{Logaritmes in het algemeen (extra)}
Dit geldt niet enkel voor 2! De logaritme in basis $a$, is het aantal keer dat je kan delen door $a$. Bijvoorbeeld:
\begin{itemize}
\item $\log_3(27) = 3$
\item $\log_4(16) = 2$
\item $\log_5(5) = 1$
\end{itemize}

~

De basis a logaritme is dus de macht waartoe je a moet verheffen om $n$ te krijgen:
\[ x = \log_a (n)\ \Leftrightarrow\ a^x = n \]
Je kan het een beetje zien als "de inverse" van machten.
\end{frame}

\begin{frame}[fragile]
\frametitle{Zoeken in een gesorteerde tabel (1)}
We krijgen een tabel die gesorteerd is volgens stijgende volgorde:
\begin{center}
\def\arraystretch{1.3}
\begin{tabu} to .7\textwidth {|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|}
\hline
1 & 4 & 6 & 9 & 15 & 23 & 24 \\
\hline
\end{tabu}
\end{center}
Ga na of een getal $x$ zich erin bevindt.

~

\textbf{Oplossing 1:} Alles overlopen, lineaire tijd, $O(n)$
\begin{lstlisting}
bool isIn(int tab[], int n, int x)
{
    for (int i = 0; i < n; i++)
        if (tab[i] == x)
            return true;
    return false;
}
\end{lstlisting}
\end{frame}

\begin{frame}
\frametitle{Zoeken in een gesorteerde tabel (2)}
We zoeken 7.

~

\textbf{Idee:} kijk in het midden en vergelijk:
\begin{center}
\def\arraystretch{1.3}
\begin{tabu} to .7\textwidth {|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|}
\hline
1 & 4 & 6 & \textbf{9} & 15 & 23 & 24 \\
\hline
\end{tabu}
\end{center}
Te groot ($9>7$), dus we gaan naar links:
\begin{center}
\def\arraystretch{1.3}
\begin{tabu} to .7\textwidth {|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|}
\hline
1 & \textbf{4} & 6 & \gray{9} & \gray{15} & \gray{23} & \gray{24} \\
\hline
\end{tabu}
\end{center}
Te klein ($4<7$), dus we gaan naar rechts:
\begin{center}
\def\arraystretch{1.3}
\begin{tabu} to .7\textwidth {|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|}
\hline
\gray{1} & \gray{4} & \textbf{6} & \gray{9} & \gray{15} & \gray{23} & \gray{24} \\
\hline
\end{tabu}
\end{center}
Maar $6\neq7$ dus 7 zit niet in de tabel.
\end{frame}

\begin{frame}[fragile]
\frametitle{Zoeken in een gesorteerde tabel (3)}
We splitsen telkens in 2, dus $\Rightarrow \log_2(n)$ pogingen nodig.

~

\textbf{Solution 2:} binair zoeken, logaritmische tijd, $O(\log n)$
\begin{lstlisting}
bool isIn(int tab[], int n, int x)
{
    int left = 0, right = n-1;
    while (left <= right)
    {
        int mid = (left+right) / 2;
        if (x < tab[mid]) right = mid - 1;
        else if (x > tab[mid]) left = mid + 1;
        else return true;
    }
    return false;
}
\end{lstlisting}
\emph{Veel} sneller!
\end{frame}

\begin{frame}
\frametitle{Praktische limieten}
Limieten voor $n$ om uit te voeren in enkele seconden:
\begin{center}
\begin{tabu}{lll}
    \toprule
    Complexiteit & Limiet voor $n$ & Voorbeeld \\
    \midrule
    $O(1), O(\log n)$ & $\leq 10^{18}$ & (Ongeveer de limiet voor een long (Java)/long long (C++) ) \\
    $O(n)$ & $\leq$ 100\,M & Een rijl overlopen \\
    $O(n\log n)$ & $\leq$ 1\,M &  Een rij sorteren \\
    $O(n^2)$ & $\leq$ 10\,k & Een geneste lus (een lus binnen een lus) \\
    \bottomrule
\end{tabu}
\end{center}
Samengevat: kijk naar de tweede kolom en deze geeft ongeveer de hoogst mogelijke complexiteit weer die je programma mag hebben.
\end{frame}

\end{document}