AT UE 01

Aufgaben: ex01-1.pdf
Lösungen: sol01-1.pdf

1.1

Data: Array $A$ mit Änderungen
Result: $i_{max}$, $j_{max}$
Pseudocode:

$i_{max}:=0$
$j_{max}:=0$
$x:=0$
$i:=0$
while $i$ < length $A$ do:
$j:=i+1$
$a:=0$
while $j$ < length $A$ do:
$x_{new}:=A_{abs}[j]-A_{abs}[i]$
if $x<x_{new}$ then
$x:=x_{new}$
$i_{max}:=i$
$j_{max}:=j$
$j:=j+1$
$i:=i+1$

return $i_{max},j_{max}$

1.2

Data: $A=[a_0,a_1,...,a_{n-1}]\in \mathbb{N}$ sortiert, $k\in \mathbb{N}$
Result: $i_{res},j_{res}:i_{res}+j_{res}=k$
Pseudocode:
$i:=0$
$j:=$ length $A-1$

while $i<j$
$x:=A[i]+A[j]$
if $x<k$ then
$i:=i+1$
else if x > k then
$j:=j-1$
else
return $i,j$

return -1

Best Case

7 Schritte
O(1)

1.3

Best case

n - 1 Vergleiche

Worst case

$\frac{n\cdot (n-1)}{2}+(n-1)$