ວິທີການຊອກຫາ theta ໃຫຍ່


ຕອບ 1:

ແນວຄວາມຄິດຂອງແນວຄິດໃຫຍ່ Theta ແມ່ນການເຮັດ ໜ້າ ທີ່ຕ່າງໆແລະຈັດວາງແຕ່ລະກຸ່ມເປັນກຸ່ມຫລື ໝວດ ໝູ່. ພວກເຮົາຕ້ອງການຢາກຮູ້ວ່າ ໜ້າ ທີ່ໃດ ໜຶ່ງ ໂດຍທົ່ວໄປແມ່ນຮູບແຂບ, ສີ່ຫລ່ຽມ, ກ້ອນ, ທ່ອນ n, n log n, ແລະອື່ນໆຈຸດປະສົງຂອງການຈັດປະເພດນີ້ແມ່ນວິທີທາງທິດສະດີ ສຳ ລັບພວກເຮົາໃນການປຽບທຽບທົ່ວໄປລະຫວ່າງສູດການຄິດໄລ່. ການຄິດໄລ່ໄລຍະເວລາຂະ ໜາດ ໃຫຍ່ Theta linear ແມ່ນການແກ້ໄຂບັນຫາ Theta n log n ໃຫຍ່, ເຊິ່ງເປັນການຕີລາຄາໃຫຍ່ຂອງ Theta n ^ 2. ໃນສູດການຄິດໄລ່ "ວັນເກົ່າ" ໄດ້ຖືກປຽບທຽບໂດຍການວັດແທກເວລາແລ່ນໃນຄອມພິວເຕີ້ຕ່າງໆ, ພາສາການຂຽນໂປແກຼມແລະເວທີຕ່າງໆ ... ໝາກ ໂປມແລະ ໝາກ ກ້ຽງ. ແນວຄວາມຄິດຂອງການປຽບທຽບລະບົບການຄິດໄລ່ໂດຍການປະຕິບັດທິດສະດີຂະ ໜາດ ໃຫຍ່ Theta ເຮັດໃຫ້ຄວາມສົມບູນຂອງສູດການຄິດໄລ່ເປັນວິທະຍາສາດ.

ໃນປັດຈຸບັນໃນການປະຕິບັດ, ການກ້າວ ໜ້າ ທີ່ຍິ່ງໃຫຍ່ນີ້ມັກຈະເຮັດວຽກໄດ້ດີແຕ່ບໍ່ແມ່ນສະ ເໝີ ໄປ. ວິທະຍາສາດຄອມພິວເຕີແມ່ນການປະສົມປະສານດ້ານຄະນິດສາດແລະວິສະວະ ກຳ ທີ່ສວຍງາມ, ແລະຄະນິດສາດຢູ່ທີ່ນີ້ບໍ່ມີຄວາມ ສຳ ຄັນໃດໆຕໍ່ວິສະວະ ກຳ. ຍົກຕົວຢ່າງ, ເຖິງແມ່ນວ່າລະບົບ algorithm 100n ໃຫຍ່ - Theta (n), ແລະດັ່ງນັ້ນມັນຈຶ່ງດີກ່ວາລະບົບ Alta ທີ່ໃຫຍ່ - Theta (n lg n), ໃນການປະຕິບັດລະບົບ algorithm (1/2) n lg n ແມ່ນໄວກວ່າ 100n ສຳ ລັບທຸກໆ n ຫນ້ອຍກວ່າ 2 ^ 200. ນັ້ນແມ່ນ, ສໍາລັບທຸກໆ n ໃນຈັກກະວານທີ່ແທ້ຈິງ.

ກໍລະນີທີ່ບໍ່ດີທີ່ສຸດແລະການປະຕິບັດກໍລະນີທີ່ດີທີ່ສຸດຂອງສູດການຄິດໄລ່ບໍ່ກ່ຽວຂ້ອງກັບ Big-theta. ນັ້ນແມ່ນຄວາມເຂົ້າໃຈຜິດ. ສູດການຄິດໄລ່ສາມາດມີການປະຕິບັດກໍລະນີທີ່ດີທີ່ສຸດກັບຄວາມສັບສົນທີ່ໃຫຍ່ທີ່ສຸດຂອງມັນແລະການປະຕິບັດກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດກັບຕົວມັນເອງ.

ນີ້ແມ່ນລາຍລະອຽດດ້ານວິຊາການ.

ຟັງຊັນ f (n) ແມ່ນ O (g (n)) ຖ້າແລະຖ້າພຽງແຕ່ຖ້າ f (n) <= cg (n) ສຳ ລັບບາງ c> 0, ສຳ ລັບ n ທັງ ໝົດ> n_0.

ຟັງຊັນ f (n) ແມ່ນ Omega (g (n)) ຖ້າແລະຖ້າພຽງແຕ່ຖ້າ f (n)> = cg (n) ສຳ ລັບບາງ c> 0, ສຳ ລັບທຸກໆ n> n_0.

ຟັງຊັນ f (n) ແມ່ນ Theta (g (n)) ຖ້າແລະຖ້າພຽງແຕ່ຖ້າ f (n) ທັງ O (g (n)) ແລະ Omega (g (n)).

ໂດຍໃຫ້ຟັງຊັນເຊັ່ນ n ^ 2-n ພວກເຮົາເວົ້າວ່າ ໜ້າ ທີ່ນີ້ແມ່ນ O (n ^ 2) ເພາະວ່າ n ^ 2-n <= (1) n ^ 2 ສຳ ລັບທຸກຄົນ n> 1. ພວກເຮົາເວົ້າວ່າ n ^ 2-n ແມ່ນໂອເມກາ (n ^ 2) ເພາະວ່າ n ^ 2-n> = (1/2) n ^ 2 ສຳ ລັບທຸກຄົນ n> 2.

ສະນັ້ນ, n ^ 2-n ແມ່ນ Theta (n ^ 2).

Big-O ແມ່ນສິ່ງທີ່ຜູກມັດດ້ານເທິງ ສຳ ລັບ ໜ້າ ທີ່ແລະ Big-Omega ແມ່ນມີຄວາມຜູກມັດຕ່ ຳ. ຖ້າຫາກວ່າທັງສອງຂອບເຂດຕົກລົງເຫັນດີ, ຫຼັງຈາກນັ້ນ, ຫນ້າທີ່ແມ່ນ sandwiched ແລະແມ່ນ Big-Theta ຂອງຫນ້າທີ່ທົ່ວໄປ.

ຕົວຢ່າງທີ່ ໜ້າ ສົນໃຈກວ່ານີ້ແມ່ນ log (n!) ເຊິ່ງແມ່ນ Theta (n log n), ເພາະວ່າ

(1/2) n log n <= log (n!) <= n log n, ສຳ ລັບທຸກໆ n> 2


ຕອບ 2:

ຕົວຈິງແລ້ວຄວາມ ໝາຍ ທີ່ໃຫຍ່ຫຼວງເຮັດໃຫ້ທ່ານມີຄວາມຜູກພັນ ແໜ້ນ. ມັນຍັງບອກອີກວ່າສູດການຄິດໄລ່ທີ່ໄດ້ຮັບນັ້ນເພິ່ງພໍໃຈທັງໃຫຍ່ -O ແລະ Big-Omega.

ເວົ້າ, f (n) ແລະ g (n) ແມ່ນ ໜ້າ ທີ່ທີ່ມີຄຸນຄ່າໃນທາງບວກເຊິ່ງຖືເອົາຄຸນຄ່າທາງບວກ 'n' ເປັນການໂຕ້ຖຽງແລ້ວຜູ້ໃຫຍ່ສາມາດຖືກ ກຳ ນົດເປັນ

Theta (g (n)) = {f (n): ມີ ຈຳ ນວນທີ່ເປັນບວກ c1, c2 ແລະ n1 ເຊັ່ນວ່າ 0 <= c1. (g (n)) <= f (n) <= c2. (g (n )) ສຳ ລັບທຸກຄົນ n> = n1}

ນັ້ນ ໝາຍ ຄວາມວ່າ f (n) ສາມາດແຊນວິດລະຫວ່າງ c1.g (n) ແລະ c2.g (n).


ຕອບ 3:

ໝາຍ ເຫດໃຫຍ່ Theta

ແນວຄວາມຄິດ theta ໃຫຍ່ແມ່ນໃຊ້ເພື່ອພັນລະນາເຖິງປະສິດທິພາບຂອງ asymptotic

ສູດການຄິດໄລ່

. ມັນຖືກຂຽນໄວ້

Θ (f (n))

ບ່ອນທີ່

n∈N

(ບາງຄັ້ງກໍ່ຕັ້ງນອກ ເໜືອ ຈາກ ຈຳ ນວນຕົວເລກ ທຳ ມະຊາດ,

, ຖືກ ນຳ ໃຊ້).

ສຳ ນວນΘ (f (n)) ແມ່ນຊຸດຂອງ ໜ້າ ທີ່ {g (n): ∃c1, c2, n0∈N, ∀n≥n0, 0≤c1f (n) ≤g (n) ≤c2f (n) }. ໃນພາສາອັງກິດ ທຳ ມະດາ, ຊຸດນີ້ແມ່ນໄດ້ຖືກປະຊາຊົນໃຊ້ໂດຍ ໜ້າ ທີ່ທີ່ຖືກແຊ່ໂດຍ c1f (n) ແລະ c2f (n). ນີ້ແມ່ນເປັນທີ່ຮູ້ຈັກວ່າເປັນການຜູກມັດທີ່ບໍ່ ແໜ້ນ ໜາ. ສຳ ລັບສະມາຊິກທີ່ ກຳ ນົດ, ພວກເຮົາຂຽນ h (n) = Θ (f (n)) ແລະບໍ່ແມ່ນ h (n) ∈Θ (f (n)).

ຕົວຢ່າງ

ບັນຊີລາຍຊື່ຂອງການສະແດງອອກແລະຂອບເຂດຂອງອັດຕາໃຫຍ່ຂອງພວກມັນແມ່ນຢູ່ຂ້າງລຸ່ມ, ແລະຢູ່ລຸ່ມບັນຊີລາຍຊື່ນີ້ແມ່ນເສັ້ນສະແດງທີ່ສະແດງເຖິງການເຕີບໃຫຍ່ຂອງບາງ ໜ້າ ທີ່.

  • 2 = Θ (1)
  • 4x + 2 = Θ (x)
  • ຂະ ໜາດ 3x2 + 4x + 2 = Θ (x2)

ເອກະສານອ້າງອີງ

TH Cormen, CE Leiserson, RL Rivest, ການແນະ ນຳ ກ່ຽວກັບສູດການຄິດໄລ່. MIT Press, 1990.


ຕອບ 4:

ຄຳ ຕອບສັ້ນໆທີ່ມີຄວາມຕັ້ງໃຈແມ່ນວ່າ f (n) = \ BigTheta (g (n)) ຖ້າ iff f ແລະ g ບໍ່ສະ ໝອງ ຈະເລີນເຕີບໂຕໃນຈັງຫວະດຽວກັນ (ຄື ໜ້າ ທີ່ຂອງຕົວ ກຳ ນົດເລກເຕັມ n); ແນ່ນອນ, ສົມມຸດຕິຖານ tacit (ຄືກັນກັບ Big-O ແລະພຽງເລັກນ້ອຍ O ແລະໃຫຍ່ / Omega) ແມ່ນວ່າ f (n) ແລະ g (n) ແມ່ນ "ເໝາະ ສົມ" ໜ້າ ທີ່ສັບສົນດ້ານລະບົບ algorithmic, ແລະໂດຍສະເພາະແມ່ນ ໜ້າ ທີ່ທີ່ບໍ່ ໜ້າ ເຊື່ອຖືຂອງ the parameter n. ໃຫ້ສັງເກດວ່າ, ບໍ່ຄືກັບ O ແລະ Omega, Theta ແມ່ນມີຄວາມ ຈຳ ເປັນຕ້ອງມີຄວາມສອດຄ່ອງ (ນັ້ນແມ່ນຖ້າ f = Theta (g) ຈາກນັ້ນກໍ່ແມ່ນ g = Theta (f)).


ຕອບ 5:

ເບິ່ງວ່າແນວຄິດໃຫຍ່ແມ່ນຫຍັງ?


ຕອບ 6:

ໝາຍ ເຫດຂອງ Theta ໃຫ້ຂໍ້ຜູກມັດທີ່ບໍ່ ແໜ້ນ ໜາ ສຳ ລັບ f (n). Θການແຈ້ງບອກແມ່ນພຽງແຕ່ຂຽນເປັນ, f (n) ΘΘ (g (n)), ບ່ອນທີ່ຂະ ໜາດ ບັນຫາແລະ

Θ (g (n)) = {h (n): ants ຄ່າຄົງທີ່ c1, c2, ແລະ n0 ເຊັ່ນນັ້ນ 0 ≤ c1 g (n) ≤ h (n) ≤ c2 g (n), ∀ n ≥ n0}.

ດັ່ງນັ້ນ, ພວກເຮົາສາມາດເວົ້າໄດ້ວ່າΘ (g (n)) ປະກອບດ້ວຍຊຸດຂອງທຸກໆ ໜ້າ ທີ່ h (n) ທີ່ຢູ່ລະຫວ່າງ c1 g (n) ແລະ c2 g (n) ສຳ ລັບຄ່າທັງ ໝົດ ຂອງ n ≥ n0.


ຕອບ 7: