يونيتي (لغة برمجة)

تُرتّب المصفوفة باستخدام خوارزمية فرز الفقاعات عن طريق مقارنة الأرقام المتجاورة، وتبديلها إذا كانت بترتيب خاطئ.${\displaystyle \Theta (n)}$الوقت المتوقع،${\displaystyle \Theta (n)}$المعالجات و${\displaystyle \Theta (n^{2})}$العمل المتوقع. السبب في أنك لا تملك سوى${\displaystyle \Theta (n)}$الوقت المتوقع ، هو الذي kيتم اختياره دائمًا بشكل عشوائي من${\displaystyle \{0,1\}}$يمكن إصلاح ذلك عن طريق قلبها kيدويًا.

برنامج فرز الفقاعات يعلن ن: عدد صحيح، أ: مصفوفة من الأعداد الصحيحة [0..n-1] بدءًا ن = 20 <|| i : 0 <= i and i < n :: A[i] = rand() % 100 > تعيين <# k : 0 <= k < 2 :: <|| i : i % 2 = k and 0 <= i < n - 1 :: A[i]، A[i+1] := A[i+1]، A[i] إذا كان A[i] > A[i+1] >> نهاية

يمكنك فرزها${\displaystyle \Theta (\log n)}$الوقت مع خوارزمية الترتيب. أنت بحاجة إلى${\displaystyle \Theta (n^{2})}$المعالجات، و${\displaystyle \Theta (n^{2})}$عمل.

برنامج فرز الترتيب يعلن ن: عدد صحيح، A,R: مصفوفة من الأعداد الصحيحة [0..n-1] بدءًا ن = 15 <|| i : 0 <= i < n :: A[i], R[i] = rand() % 100, i > تعيين <|| i : 0 <= i < n :: R[i] := <+ j : 0 <= j < n and (A[j] < A[i] or (A[j] = A[i] and j < i)) :: 1 >> 8 <|| i : 0 <= i < n :: A[R[i]] := A[i] > نهاية

باستخدام خوارزمية فلويد-وارشال لأقصر مسار بين جميع الأزواج ، نقوم بتضمين العقد الوسيطة بشكل متكرر، ونحصل على${\displaystyle \Theta (n)}$الوقت، باستخدام${\displaystyle \Theta (n^{2})}$المعالجات و${\displaystyle \Theta (n^{3})}$عمل.

أقصر مسار في البرنامج يعلن n، k: عدد صحيح، D: مصفوفة من الأعداد الصحيحة [0..n-1, 0..n-1] بدءًا ن = 10 k = 0 <|| i,j : 0 <= i < n and 0 <= j < n :: D[i,j] = rand() % 100 > تعيين <|| i,j : 0 <= i < n and 0 <= j < n :: D[i,j] := min(D[i,j], D[i,k] + D[k,j]) > || k := k + 1 إذا كان k < n - 1 نهاية

يمكننا القيام بذلك بشكل أسرع. يحسب البرنامج التالي أقصر مسار بين جميع الأزواج في${\displaystyle \Theta (\log ^{2}n)}$الوقت، باستخدام${\displaystyle \Theta (n^{3})}$المعالجات و${\displaystyle \Theta (n^{3}\log n)}$عمل.

برنامج shortestpath2 يعلن ن: عدد صحيح، D: مصفوفة من الأعداد الصحيحة [0..n-1, 0..n-1] بدءًا ن = 10 <|| i,j : 0 <= i < n and 0 <= j < n :: D[i,j] = rand() % 10 > تعيين <|| i,j : 0 <= i < n and 0 <= j < n :: D[i,j] := min(D[i,j], <min k : 0 <= k < n :: D[i,k] + D[k,j] >) > نهاية

بعد الجولة${\displaystyle r}$، D[i,j]يحتوي على طول أقصر مسار من${\displaystyle i}$ل${\displaystyle j}$من الطول${\displaystyle 0\dots r}$في الجولة التالية، ذات الطول${\displaystyle 0\dots 2r}$وهكذا دواليك.