-3
Angenommen, es gibt einen Job und viele Mitarbeiter sind verfügbar. Der folgende Code ist möglicherweise eine schlechte Optimierungsidee. Aber es ist nur für die Analyse der Komplexität.Rechnerische Komplexität unbekannter Wahrscheinlichkeit
A is a set of N worker
while (A is not empty)
{
B=empty set
foreach a1 in A
{
foreach a2 in A
{
b= merge(a1, a2)
if (b works better than a1 **and** b works better than a2)
add b to B
}
}
A=B
}
Das Problem ist, dass die Wahrscheinlichkeit von „b funktioniert besser als a1 und a2“ ist nicht bekannt. Also, wie die Zeit Komplexität des obigen Codes zu schätzen?
was 'merge()', was ist 'B'? – fjardon
Sieht aus wie Operationen mit konstanter Zeit. Es ist also egal. –
@ Nico Schertler. Danke, dass Sie auf das Problem hingewiesen haben. Ich habe den Code korrigiert, A wird innerhalb der while-Schleife aktualisiert. merge() bedeutet, dass a1 und a2 zu einer Gruppe von Arbeitern zusammengefasst werden. Das heißt, "A" enthält zunächst eine Gruppe einzelner Arbeiter. Dann enthält 'A' nach und nach größere Gruppen. Angenommen, die Komplexität wird als Anzahl der if-Anweisungen gezählt. –