Информатика · ҰБТ сұрағы №12574

Алгоритмді оның уақыт күрделілігімен (ең нашар жағдайда, n — элемент саны) сәйкестендіріңіз.

  1. Реттелген массивте екілік іздеу
  2. Реттелмеген массивте тізбектей іздеу
  3. Көпіршікті сұрыптау
  4. Біріктіру арқылы сұрыптау (merge sort)
  • A) O(2ⁿ)
  • B) O(n log n)
  • C) O(1)
  • D) O(n)
  • E) O(log n)
  • F) O(n²)
Дұрыс жауабы мен түсіндірмесі
Жауабы: Реттелген массивте екілік іздеу — O(log n); Реттелмеген массивте тізбектей іздеу — O(n); Көпіршікті сұрыптау — O(n²); Біріктіру арқылы сұрыптау (merge sort) — O(n log n)

Екілік іздеу аралықты әр қадамда екіге бөледі — log n; тізбектей іздеу n рет салыстырады; көпіршікті сұрыптау екі ішкі цикл — n²; merge sort — n log n.

«Алгоритмдер және программалау» тақырыбынан тағы