الوحدة 3 · CS353

🎯 أهداف التعلم

$$C(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1 = \frac{(n-1)n}{2}$$
Pseudocode
ALGORITHM SelectionSort(A[0..n-1])
for i <- 0 to n-2 do
  min <- i
  for j <- i+1 to n-1 do
    if A[j] < A[min] min <- j
  swap A[i] and A[min]
🗺️ Selection Sort
$$C(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-2-i} 1 = \frac{(n-1)n}{2} \in O(n^2)$$
Pseudocode
ALGORITHM BubbleSort(A[0..n-1])
for i <- 0 to n-2 do
  for j <- 0 to n-2-i do
    if A[j+1] < A[j] swap A[j] and A[j+1]
🗺️ Bubble Sort
Selection Sort Bubble Sort
$$m(n - m + 1) \in O(nm)$$
Pseudocode
ALGORITHM BruteForceStringMatch(T[0..n-1], P[0..m-1])
for i <- 0 to n-m do
  j <- 0
  while j < m and P[j] == T[i+j] do
    j <- j + 1
  if j == m return i
return -1
🗺️ Brute-Force String Matching
$$C(n) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1 = \frac{(n-1)n}{2} \in O(n^2)$$
Pseudocode
ALGORITHM BruteForceClosestPair(P)
d <- infinity
for i <- 1 to n-1 do
  for j <- i+1 to n do
    d <- min(d, sqrt((x_i - x_j)^2 + (y_i - y_j)^2))
return d
🗺️ Closest-Pair Problem
$$\frac{(n-1)!}{2}$$
🗺️ Traveling Salesman Problem (TSP)
$$O(2^n)$$
🗺️ Knapsack Problem
$$O(n!)$$
🗺️ Assignment Problem
🎓

حديث البروفيسور

❓ اسأل البروفيسور

البطاقات التعليمية

اختبر نفسك

1 / 10 🎯 نتيجتك: 0

🔐 خزنة الامتحان

⚠️ TRAP
🤫 SECRET
🔑 KEY_CONCEPT
⚠️ TRAP