ບົດທີ 4 Big O

Big O Notation ໃຊ້ເພື່ອຫຍັງ?

• ວັດແທກເວລາປະຕິບັດງານທີ່ແທ້ຈິງຂອງໂປຣແກຣມ

• ອະທິບາຍການຂະຫຍາຍຕົວຂອງຊັບພະຍາກອນທີ່ອັນກໍຣິທຶມຕ້ອງການເມື່ອຂະໜາດຂໍ້ມູນປ່ຽນແປງ

• ບອກຈຳນວນແຖວຂອງໂປຣແກຣມໃນໂປຣແກຣມ

• ກຳນົດຄວາມສັບສົນຂອງໂປຣແກຣມ

Big O ຂອງການເຂົ້າເຖິງອົງປະກອບໃນອາເຣໂດຍໃຊ້ອິນເດັກ (index) ແມ່ນຫຍັງ?

• O(n)

• O(log n)

• O(1)

• O(n^2)

ອັນກໍຣິທຶມໃດມີ Big O ຂອງ O(log n)?

• Linear Search

• Bubble Sort

• Binary Search

• Insertion Sort

ຖ້າອັນກໍຣິທຶມໜຶ່ງໃຊ້ເວລາ 1 ວິນາທີເພື່ອປະມວນຜົນຂໍ້ມູນຂະໜາດ 1000 ລາຍການ, ແລະ ມີ Big O ເປັນ O(n^2), ມັນຈະໃຊ້ເວລາເທົ່າໃດໂດຍປະມານເພື່ອປະມວນຜົນຂໍ້ມູນຂະໜາດ 2000 ລາຍການ?

• 1 ວິນາທີ

• 2 ວິນາທີ

• 4 ວິນາທີ

• 8 ວິນາທີ

ໃນ Big O Notation, ເຮົາຄວນເອົາໃຈໃສ່ຫຍັງເປັນອັນດັບຕົ້ນໆ?

• ຄ່າຄົງທີ່ (Constants)

• ພົດທີ່ນ້ອຍກວ່າ (Smaller terms)

• ການດຳເນີນງານຫຼັກ (Dominant operations)

• ທຸກຢ່າງເທົ່າທຽມກັນ

ໂປຣແກຣມຕໍ່ໄປນີ້ມີ Big O ເທົ່າໃດ?

for i in range(n):

print(i)

• O(1)

• O(log n)

• O(n)

• O(n^2)

Big O Notation ສຸມໃສ່ກໍລະນີໃດ?

• ກໍລະນີທີ່ດີທີ່ສຸດ (Best-case)

• ກໍລະນີສະເລ່ຍ (Average-case)

• ກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດ (Worst-case)

• ທຸກໆກໍລະນີເທົ່າທຽມກັນ

ອັນກໍຣິທຶມການຈັດຮຽງໃດມີ Big O ສະເລ່ຍຂອງ O(n log n)?

• Bubble Sort

• Insertion Sort

• Merge Sort

• Selection Sort

ເສັ້ນສະແດງໃດສະແດງເຖິງການຂະຫຍາຍຕົວທີ່ໄວທີ່ສຸດເມື່ອ n ເພີ່ມຂຶ້ນ?

• O(n)

• O(log n)

• O(n^2)

• O(1)

Big O ຂອງການວົນຊ້ຳສອງຊັ້ນ (nested loops) ຜ່ານອາເຣຂະໜາດ n ແມ່ນຫຍັງ?

• O(n)

• O(log n)

• O(n log n)

• O(n^2)