Vertragstheorie Eine Einführung mit finanzökonomischen Beispielen und Anwendungen 2005, XVI, 218 S. Basler, Herbert Grundbegriffe der Wahrscheinlichkeitsrechnung und Statistischen Methodenlehre



Download 2,57 Mb.
Pdf ko'rish
bet22/50
Sana11.09.2021
Hajmi2,57 Mb.
#171395
1   ...   18   19   20   21   22   23   24   25   ...   50
Bog'liq
Grundlagen der Wirtschaftsinformatik mit 16 Tabellen

2.1.2 Komplexit¨

at

ahrend im Zusammenhang mit der Berechenbarkeitstheorie Existenzaussa-



gen im Mittelpunkt stehen, untersucht die Algorithmen- und Komplexit¨

ats-

theorie Fragestellungen hinsichtlich des Aufwandes, der zur Berechnung eines

Problems anf¨

allt.

7

Dabei stehen Aussagen bez¨



uglich der Rechenzeit (Rechen-

aufwand, Laufzeit) im Mittelpunkt – weitere Ressourcen sind z. B. Speicher-

platz oder Kommunikationsaufwand –, wobei in der Regel die Anzahl aus-

gef¨


uhrter Elementaroperationen als Berechnungs- bzw. Messgr¨

oße zu Grunde

gelegt wird (wie z. B. Addition oder Vergleich zweier Zahlen mit begrenzter

Stellenzahl).

Zur Quantifizierung der Laufzeit von Algorithmen verwendet man in der

Regel die asymptotische Laufzeitkomplexit¨



at. Dabei begn¨

ugt man sich unter

Verwendung der so genannten O-Notation mit

groben“ Aussagen zum Lauf-



zeitverhalten



ur große n“, wobei die Problemgr¨oße beschreibt. Oftmals

erscheint die Angabe der Problemgr¨

oße offensichtlich. So mag sich die Be-

schreibung der Problemgr¨

oße f¨

ur die Sortierung von Zahlen durch sofort



aufdr¨

angen; allerdings bleibt dabei unber¨

ucksichtigt, dass sich f¨

ur jede ein-

zelne Zahl in Abh¨

angigkeit von der Gr¨

oße oder der Genauigkeit eventuell

ein nicht konstanter Speicheraufwand ergibt. Als weiteres Beispiel diene die

Addition zweier n × n Matrizen: Obwohl die Eingabel¨ange hierf¨ur eigentlich

2

· n · n · d betr¨agt, wobei die ben¨otigte Speicherl¨ange f¨ur ein Matrixele-

ment ist, gibt man den Berechnungsaufwand in der Regel f¨

ur den prim¨

ar

kennzeichnenden Parameter an.



Eine asymptotische Laufzeitkomplexit¨

at von (n) = O(n

2

) bedeutet, dass



die Laufzeit eines Algorithmus f¨

ur gen¨


ugend große Werte von durch eine

Funktion c · n

2

konstant, nach oben beschr¨ankt ist. Formal l¨asst sich dies



folgendermaßen spezifizieren: (n) = O((n)) ⇔ ∃c > ∃n



∀n > n



:

(n≤ c · f (n). Einige typische Laufzeitklassen seien im Folgenden kurz

charakterisiert:

7

Vgl. hierzu z. B. Bachem (1980), Engesser (1993), Garey und Johnson (1979),



Papadimitriou (1994), Rechenberg (2000) und Wegener (1999).


18

2. Informatik und Informations- und Kommunikationstechnik



• O(1), konstanter Aufwand: Die Laufzeit ist konstant bzw. von der Prob-

lemgr¨


oße unabh¨

angig.


• O(log n), logarithmische Komplexit¨at: Eine Verdopplung der Eingabegr¨oße

des Problems f¨

uhrt hier nur zu einem Anstieg der Laufzeit um eine Kon-

stante. Ein Beispiel f¨

ur einen solchen Algorithmus ist die bin¨

are Suche

eines Elementes in einer geordneten Sequenz von Zahlen (sukzessive ver-

gleichend mit einem mittleren Element der verbliebenen Sequenz werden

die zu betrachtenden Zahlen in jedem Schritt in etwa halbiert).

• O(n), lineare Komplexit¨at: Die Laufzeit ist proportional zur Problemgr¨oße.

Beispiel: Suche eines Elementes in einer ungeordneten Menge von Zahlen.



• O(log n): Diese Laufzeitkomplexit¨at ist typisch f¨ur Algorithmen zur Sor-

tierung von Objekten.



• O(n

k

), konstant, polynomiale Komplexit¨at: Solche Laufzeitkomple-

xit¨

aten sind typisch f¨



ur Algorithmen mit geschachtelten Schleifen, die

jeweils mit einer von abh¨angigen H¨aufigkeit durchlaufen werden.



• O(2

n

), exponentielle Komplexit¨

at: Die Laufzeit solcher Algorithmen

achst so stark an, dass sie f¨



ur

große n“ nicht mehr brauchbar sind.



Die asymptotische Laufzeitkomplexit¨

at charakterisiert das Laufzeitver-

halten eines Algorithmus nur grob. Weiterhin wird bei solchen Aussagen in

der Regel der Worst Case angenommen; d. h. es wird eine obere Absch¨

atzung



ur den schlimmstm¨



oglichen Fall getroffen. Im praktischen Einsatz kann da-

mit ein Verfahren mit einer Komplexit¨

at von O(n

2

) im Durchschnitt besser



abschneiden als eines mit O(log n). Dies sei an folgendem Beispiel verdeut-

licht: Als Sortieralgorithmus wird h¨

aufig der Quicksort-Algorithmus einge-

setzt; vgl. z. B. Cormen et al. (2004). Es gibt einige Eingaben, f¨

ur die der

Quicksort-Algorithmus zur Sortierung von Zahlen eine Laufzeit von O(n

2

)

ben¨



otigt; zumeist liegt die Laufzeit aber bei O(log n). Da der Quicksort-

Algorithmus relativ einfach zu implementieren und die im großen O

versteck-



te“ Konstante relativ klein ist, wird dieser Algorithmus in der praktischen

Anwendung oft anderen Sortieralgorithmen vorgezogen, die eine Worst-Case-

Komplexit¨

at von O(log n) besitzen.

Die Vorteilhaftigkeit eines Verfahrens ist damit eigentlich eher ¨

uber die


durchschnittliche Laufzeit zu bewerten (Average Case). Allerdings ergeben

sich hierbei im Allgemeinen zwei Probleme: Zum einen ist die Kenntnis der

Wahrscheinlichkeitsverteilung der Eingaben notwendig, zum anderen ergeben

sich in der Regel bei nichttrivialen Algorithmen erhebliche Schwierigkeiten bei

der Bestimmung des durchschnittlichen Berechnungsaufwandes.

Eine weitere relevante M¨

oglichkeit der Quantifizierung des Berechnungs-

aufwandes besteht in der amortisierten Laufzeitanalyse, bei der der Aufwand

einer wiederholten Ausf¨

uhrung gewisser Operationen berechnet wird. Dies sei

durch ein Beispiel erl¨

autert: Obwohl der Aufwand einer einzelnen Operation

im Worst Case linear sein mag (z. B. die Erweiterung eines Vektors um ein

Element ¨

uber den bereits reservierten Speicherbereich hinaus), k¨

onnen nach-

folgende Operationen oftmals mit konstantem Aufwand ausgef¨

uhrt werden




2.1 Theoretische Grundlagen

19

(z. B. indem eine n¨



otige Erweiterung eines Vektors ¨

uber eine Verdopplung

des reservierten Speicherbereiches durchgef¨

uhrt wird), so dass sich amorti-

siert ein konstanter Aufwand f¨

ur die Operationsausf¨

uhrung ergeben kann.

Zur Verdeutlichung der Auswirkungen verschiedener Laufzeitkomplexi-

aten kann Tabelle 2.1 dienen, die f¨



ur gewisse Laufzeitkomplexit¨

aten und


Rechenzeiten die maximal l¨

osbare Problemgr¨

oße angibt. Dabei sei davon

ausgegangen, dass in einer Millisekunde eine Elementaroperation ausgef¨

uhrt

wird. Man erkennt, dass insbesondere bei der exponentiellen Laufzeitkomple-



xit¨

at eine Erh¨

ohung der Rechenzeit nur relativ geringe Auswirkungen auf die

osbare Problemgr¨



oße nach sich zieht.

Rechenzeit

Komplexit¨

at 1 Sekunde

1 Minute

1 Stunde


n

= 1.000 = 60.000 = 3.600.000

n

2

= 31,6



= 244,9

= 1.897,4

2

n



= 10,0

= 15,9

= 21,8


Download 2,57 Mb.

Do'stlaringiz bilan baham:
1   ...   18   19   20   21   22   23   24   25   ...   50




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish