Sortieralgorithmen und O-Notation

Hi,

ich habe folgende 2 Fragen:

1. Welchen Aufwand hat folgender Codeschnipsel:

for (int i=n; i>1;i=i/2

)

Ich würde sagen: O(n) richtig?

Warum der Binary Insertion Sort nicht unbedingt schneller als der Insertion Sort ist.

Meine Antwort:
Der Binary Insertion Sort benutzt eine binäre Suche. Der Insertion Sort eine Linieare. Der BIS ist nur dann schnell, wenn die Felder bereits sortiert sind.
Sind die Felder schon sortiert, dann ist der IS auch schnell. Beide haben O(n^2)
richtig?

Gruß

dabudai

Bashar

dabudai schrieb:

1. Welchen Aufwand hat folgender Codeschnipsel:
for (int i=n; i>1;i=i/2
)

Ich würde sagen: O(n) richtig?

Ja, und O(n^5) würde auch stimmen. Ich schätze aber mal, dass nach einer genauen Angabe (=> Θ) gefragt ist. Simulier es doch mal für einige Werte von Hand durch und stell eine Vermutung auf.

Der Binary Insertion Sort benutzt eine binäre Suche. Der Insertion Sort eine Linieare. Der BIS ist nur dann schnell, wenn die Felder bereits sortiert sind.
Sind die Felder schon sortiert, dann ist der IS auch schnell. Beide haben O(n^2)
richtig?

Ein Sortieralgorithmus, der nur auf sortierten Feldern funktioniert, wäre irgendwie unsinnig. Es wird natürlich nur auf der bereits sortierten Teilsequenz binär gesucht.
Der Grund, warum der BIS trotzdem Ω(n^2) Aufwand hat, ist ein anderer.

Tachyon

Zu 1: Flasch. Die Komplexität ist O(log(n)).

C++ Forumbot

Dieser Thread wurde von Moderator/in volkard aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Tachyon schrieb:

Zu 1: Flasch. Die Komplexität ist O(log(n)).

Könntest du mir auch verraten warum das so ist?

volkard

dabudai schrieb:

Tachyon schrieb:

Zu 1: Flasch. Die Komplexität ist O(log(n)).

Könntest du mir auch verraten warum das so ist?

wegen i=i/2

für n=2^x braucht er x durchläufe, bis er zie zahl runterhalbiert hat.
dann müßte er für n=n also x=log(n) durchläufe brauchen.

Simulier es doch mal für einige Werte von Hand durch und stell eine Vermutung auf.