ความซับซ้อนของอัลกอริทึม

สวัสดี! การบรรยายในวันนี้จะแตกต่างจากที่อื่นเล็กน้อย มันจะแตกต่างตรงที่มันเกี่ยวข้องทางอ้อมกับ Java เท่านั้น อย่างไรก็ตาม หัวข้อนี้มีความสำคัญมากสำหรับโปรแกรมเมอร์ทุกคน เราจะพูดถึง อั ลกอริทึม อัลกอริทึมคืออะไร? กล่าวง่ายๆนี่คือลำดับการกระทำบางอย่างที่ต้องดำเนินการเพื่อให้ได้ผลลัพธ์ที่ต้องการ . เรามักใช้อัลกอริธึมในชีวิตประจำวัน ตัวอย่างเช่น ทุกเช้าคุณจะพบกับงาน: ไปโรงเรียนหรือที่ทำงาน และในขณะเดียวกันก็ต้อง:

• แต่งตัว
• ทำความสะอาด
• เลี้ยงอย่างดี

อัลกอริทึมใดที่จะช่วยให้คุณบรรลุผลลัพธ์นี้

1. ตื่นขึ้นมาด้วยนาฬิกาปลุก
2. อาบน้ำล้างหน้า.
3. เตรียมอาหารเช้า ชงกาแฟ/ชา
4. กิน.
5. หากคุณไม่ได้รีดเสื้อผ้าตั้งแต่ตอนเย็นก็รีดผ้าซะ
6. แต่งตัว.
7. ออกจากบ้าน.

ลำดับการกระทำนี้จะช่วยให้คุณได้รับผลลัพธ์ที่ต้องการอย่างแน่นอน ในการเขียนโปรแกรม งานทั้งหมดของเราคือการแก้ปัญหาอย่างต่อเนื่อง ส่วนสำคัญของงานเหล่านี้สามารถทำได้โดยใช้อัลกอริธึมที่รู้จักอยู่แล้ว ตัวอย่างเช่น คุณกำลังเผชิญกับงาน: จัดเรียงรายชื่อ 100 ชื่อในอาร์เรย์ งานนี้ค่อนข้างง่าย แต่สามารถแก้ไขได้หลายวิธี ต่อไปนี้เป็นวิธีแก้ไขปัญหาหนึ่ง: อัลกอริทึมสำหรับการเรียงลำดับชื่อตามตัวอักษร:

1. ซื้อหรือดาวน์โหลดบนอินเทอร์เน็ต "พจนานุกรมชื่อส่วนตัวของรัสเซีย" ฉบับปี 1966
2. ค้นหาทุกชื่อในรายการของเราในพจนานุกรมนี้
3. จดลงบนกระดาษว่าชื่อนั้นอยู่ในหน้าใดของพจนานุกรม
4. เรียงชื่อตามลำดับโดยใช้บันทึกย่อบนแผ่นกระดาษ

ลำดับการกระทำดังกล่าวจะทำให้เราสามารถแก้ไขปัญหาของเราได้หรือไม่? ใช่ มันจะยอมให้มันเต็มที่ วิธีแก้ปัญหานี้จะได้ผล หรือไม่ ? แทบจะไม่. เรามาถึงคุณสมบัติที่สำคัญอีกอย่างหนึ่งของอัลกอริธึม- ประสิทธิภาพ ปัญหาสามารถแก้ไขได้หลายวิธี แต่ทั้งในด้านการเขียนโปรแกรมและในชีวิตประจำวันเราเลือกวิธีที่จะมีประสิทธิภาพมากที่สุด หากงานของคุณคือทำแซนด์วิชด้วยเนย คุณสามารถเริ่มต้นด้วยการหว่านข้าวสาลีและรีดนมวัว แต่นี่จะเป็น วิธีแก้ปัญหา ที่ไม่ได้ผล - จะใช้เวลานานและเสียเงินเป็นจำนวนมาก เพื่อแก้ปัญหาง่ายๆ ของคุณ คุณสามารถซื้อขนมปังและเนยได้เลย และอัลกอริธึมกับข้าวสาลีและวัวแม้ว่าจะช่วยให้คุณสามารถแก้ปัญหาได้ แต่ก็ซับซ้อนเกินกว่าจะนำไปใช้ในทางปฏิบัติได้ เพื่อประเมินความซับซ้อนของอัลกอริธึมในการเขียนโปรแกรม มีการสร้างสัญกรณ์พิเศษที่เรียกว่าBig -O (“big O”) Big-O ช่วยให้คุณสามารถประมาณระยะเวลาดำเนิน การของอัลกอริทึมขึ้นอยู่กับข้อมูลที่ส่งเข้าไป ลองดูตัวอย่างที่ง่ายที่สุด - การถ่ายโอนข้อมูล ลองนึกภาพว่าคุณจำเป็นต้องส่งข้อมูลบางอย่างในรูปแบบของไฟล์ในระยะทางไกล (เช่น 5,000 กิโลเมตร) อัลกอริธึมใดจะมีประสิทธิภาพมากที่สุด? ขึ้นอยู่กับข้อมูลที่เขาต้องทำงานด้วย ตัวอย่างเช่น เรามีไฟล์เสียงขนาด 10 เมกะไบต์ ในกรณีนี้ อัลกอริธึมที่มีประสิทธิภาพมากที่สุดคือการถ่ายโอนไฟล์ผ่านทางอินเทอร์เน็ต ใช้เวลาเพียงไม่กี่นาที! เรามาพูดอัลกอริทึมของเราอีกครั้ง: “หากคุณต้องการถ่ายโอนข้อมูลในรูปแบบไฟล์ในระยะทาง 5,000 กิโลเมตร คุณต้องใช้การส่งข้อมูลผ่านอินเทอร์เน็ต” ยอดเยี่ยม. ทีนี้มาวิเคราะห์กัน มันแก้ปัญหาของเราได้ไหม? โดยทั่วไปแล้ว ใช่ มันแก้ปัญหาได้อย่างสมบูรณ์ แต่คุณจะพูดอะไรเกี่ยวกับความซับซ้อนของมันได้บ้าง? อืม นี่คือสิ่งที่น่าสนใจ ความจริงก็คืออัลกอริทึมของเราขึ้นอยู่กับข้อมูลที่เข้ามาเป็นอย่างมาก ซึ่งก็คือขนาดของไฟล์ ตอนนี้เรามี 10 เมกะไบต์และทุกอย่างเรียบร้อยดี จะเกิดอะไรขึ้นหากเราต้องการถ่ายโอนข้อมูลขนาด 500 เมกะไบต์? 20 กิกะไบต์? 500 เทราไบต์? 30 เพตะไบต์? อัลกอริธึมของเราจะหยุดทำงานหรือไม่? ไม่ได้ ข้อมูลจำนวนทั้งหมดนี้ยังสามารถถ่ายโอนได้ จะใช้เวลาอีกนานไหมกว่าจะเสร็จ? ใช่! ฉันจะ! ตอนนี้เรารู้ถึงคุณลักษณะที่สำคัญของอัลกอริทึมของเราแล้ว: ยิ่งขนาดของข้อมูลที่จะถ่ายโอนมีขนาดใหญ่เท่าใด อัลกอริธึมก็จะใช้เวลานานขึ้นในการดำเนินการให้เสร็จสิ้น แต่เราต้องการเข้าใจให้ชัดเจนยิ่งขึ้นว่าความสัมพันธ์นี้มีลักษณะอย่างไร (ระหว่างขนาดของข้อมูลและเวลาที่ใช้ในการถ่ายโอน) ในกรณีของเรา ความซับซ้อนของอัลกอริทึมจะเป็นเส้นตรง. “เชิงเส้น” หมายความว่าเมื่อปริมาณข้อมูลเพิ่มขึ้น เวลาในการส่งข้อมูลจะเพิ่มขึ้นตามสัดส่วนโดยประมาณ หากมีข้อมูลมากกว่า 2 เท่า และจะใช้เวลาในการถ่ายโอนเพิ่มขึ้น 2 เท่า หากมีข้อมูลมากกว่า 10 เท่า เวลาในการถ่ายโอนจะเพิ่มขึ้น 10 เท่า การใช้สัญลักษณ์ Big-O ความซับซ้อนของอัลกอริทึมของเราถูกกำหนดเป็นO(N ) สัญกรณ์นี้จำได้ดีที่สุดสำหรับการอ้างอิงในอนาคต โดยจะใช้เสมอสำหรับอัลกอริทึมที่มีความซับซ้อนเชิงเส้น โปรดทราบ: เราไม่ได้พูดถึงสิ่งต่าง ๆ ที่มี "ตัวแปร" เลย: ความเร็วอินเทอร์เน็ต พลังของคอมพิวเตอร์ของเรา และอื่นๆ เมื่อประเมินความซับซ้อนของอัลกอริทึม สิ่งนี้ไม่สมเหตุสมผลเลย เราไม่สามารถควบคุมมันได้อยู่แล้ว Big-O ประเมินอัลกอริธึมด้วยตัวเอง โดยไม่คำนึงถึง "สภาพแวดล้อม" ที่อัลกอริธึมจะต้องทำงาน มาดูตัวอย่างของเรากันต่อ สมมติว่าในที่สุดปรากฎว่าขนาดของไฟล์ที่จะถ่ายโอนคือ 800 เทราไบต์ ถ้าเราส่งข้อมูลเหล่านั้นทางอินเทอร์เน็ต ปัญหาก็จะได้รับการแก้ไขอย่างแน่นอน มีปัญหาเพียงอย่างเดียวคือ การส่งข้อมูลผ่านลิงก์สมัยใหม่มาตรฐาน (ที่ 100 เมกะบิตต่อวินาที) ที่พวกเราส่วนใหญ่ใช้ในบ้านจะใช้เวลาประมาณ 708 วัน เกือบ 2 ปี! :O ดังนั้น อัลกอริทึมของเราจึงไม่เหมาะกับที่นี่อย่างชัดเจน เราต้องการวิธีแก้ปัญหาอื่น! ทันใดนั้น Amazon ยักษ์ใหญ่ด้านไอทีก็เข้ามาช่วยเหลือเรา! บริการ Amazon Snowmobile ช่วยให้คุณสามารถโหลดข้อมูลจำนวนมากลงในหน่วยจัดเก็บข้อมูลมือถือ และส่งไปยังที่อยู่ที่ต้องการโดยรถบรรทุก! ดังนั้นเราจึงมีอัลกอริธึมใหม่! “หากคุณต้องการถ่ายโอนข้อมูลในรูปแบบไฟล์ในระยะทาง 5,000 กิโลเมตร และกระบวนการจะใช้เวลามากกว่า 14 วันในการถ่ายโอนทางอินเทอร์เน็ต คุณต้องใช้การขนส่งด้วยรถบรรทุกของ Amazon” ตัวเลขของ 14 วันถูกสุ่มเลือกที่นี่ สมมติว่านี่คือช่วงเวลาสูงสุดที่เราสามารถจ่ายได้ มาวิเคราะห์อัลกอริทึมของเรากัน แล้วความเร็วล่ะ? แม้ว่ารถบรรทุกจะเดินทางด้วยความเร็วเพียง 50 กม./ชม. แต่ก็สามารถวิ่งได้ 5,000 กม. ในเวลาเพียง 100 ชั่วโมง นั่นก็สี่วันกว่าแล้ว! นี่ดีกว่าตัวเลือกการรับส่งข้อมูลทางอินเทอร์เน็ตมาก แล้วความซับซ้อนของอัลกอริทึมนี้ล่ะ? มันจะเป็นแบบเชิงเส้นด้วยหรือไม่ O(N)? ไม่มันจะไม่ อย่างไรก็ตาม รถบรรทุกไม่สนใจว่าคุณจะบรรทุกได้มากน้อยเพียงใด รถบรรทุกจะยังคงขับด้วยความเร็วเท่าเดิมและมาถึงตรงเวลา ไม่ว่าเราจะมีข้อมูลขนาด 800 เทราไบต์ หรือมีข้อมูลมากกว่า 10 เท่า รถบรรทุกก็ยังจะไปถึงที่นั่นภายใน 5 วัน กล่าวอีกนัยหนึ่ง อัลกอริธึมในการส่งข้อมูลผ่านรถบรรทุกมีความซับซ้อนคงที่ “คงที่” หมายความว่าไม่ขึ้นอยู่กับข้อมูลที่ส่งไปยังอัลกอริทึม ใส่แฟลชไดรฟ์ขนาด 1GB ไว้ในรถบรรทุก และจะมาถึงใน 5 วัน ใส่ดิสก์ที่มีข้อมูล 800 เทราไบต์ที่นั่น และจะมาถึงใน 5 วัน เมื่อใช้ Big-O ความซับซ้อนคงที่จะแสดงเป็นO(1 ) เนื่องจากเราได้รู้จักกับO(N)และO(1)ตอนนี้เรามาดูตัวอย่าง "โปรแกรมเมอร์" เพิ่มเติมกัน :) สมมติว่าคุณได้รับอาร์เรย์จำนวน 100 หมายเลข และงานคือพิมพ์ตัวเลขแต่ละตัวลงบนคอนโซล คุณเขียนลูปปกติforที่ทำงานนี้

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

อัลกอริธึมการเขียนมีความซับซ้อนอย่างไร? เชิงเส้น, O(N) จำนวนการกระทำที่โปรแกรมต้องทำนั้นขึ้นอยู่กับจำนวนตัวเลขที่ส่งเข้าไป หากมีตัวเลข 100 ตัวในอาร์เรย์ จะมีการดำเนินการ 100 รายการ (เอาต์พุตบนหน้าจอ) หากมีตัวเลข 10,000 รายการในอาร์เรย์ จะต้องดำเนินการ 10,000 รายการ อัลกอริทึมของเราสามารถปรับปรุงได้หรือไม่? เลขที่ ไม่ว่าในกรณีใด เราจะต้องทำให้N ส่งผ่านอาเรย์และส่งออก N เอาต์พุตไปยังคอนโซล ลองดูอีกตัวอย่างหนึ่ง

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

เรามีอันว่างLinkedListซึ่งเราใส่ตัวเลขหลายตัวลงไป เราจำเป็นต้องประมาณความซับซ้อนของอัลกอริทึมในการแทรกตัวเลขตัวเดียวลงในLinkedListตัวอย่างของเรา และจะขึ้นอยู่กับจำนวนองค์ประกอบในรายการอย่างไร คำตอบคือO(1) - ความซับซ้อนคงที่ ทำไม โปรดทราบ: ทุกครั้งที่เราใส่ตัวเลขที่จุดเริ่มต้นของรายการ นอกจากนี้ ตามที่คุณจำได้ว่าเมื่อใส่ตัวเลขลงในLinkedListองค์ประกอบ ตัวเลขเหล่านั้นจะไม่ถูกเลื่อนไปที่ใดเลย - ลิงก์จะถูกกำหนดใหม่ (หากคุณลืมวิธีการทำงานของ LinkedList โดยกะทันหัน โปรดดูการบรรยายเก่ารายการ หนึ่งของเรา ) ถ้าตอนนี้ตัวเลขแรกในรายการของเราคือตัวเลขхและเราใส่ตัวเลข y ไว้ที่จุดเริ่มต้นของรายการ สิ่งที่จำเป็นต้องมีคือ:

x.previous  = y;
y.previous = null;
y.next = x;

สำหรับคำจำกัดความของการอ้างอิงนี้ใหม่ไม่สำคัญสำหรับเราว่าตอนนี้มีตัวเลขอยู่กี่ตัวLinkedListอย่างน้อยหนึ่งหรืออย่างน้อยหนึ่งพันล้าน ความซับซ้อนของอัลกอริทึมจะคงที่ - O(1)

ความซับซ้อนของลอการิทึม

อย่าตื่นตกใจ! :) หากคำว่า “ลอการิทึม” ทำให้คุณต้องการปิดการบรรยายและไม่อ่านต่อ ให้รอสักครู่ จะไม่มีปัญหาทางคณิตศาสตร์ที่นี่ (มีคำอธิบายมากมายในที่อื่น) และเราจะวิเคราะห์ตัวอย่างทั้งหมด "บนนิ้ว" ลองนึกภาพว่างานของคุณคือค้นหาหมายเลขใดหมายเลขหนึ่งในอาร์เรย์จำนวน 100 หมายเลข แม่นยำยิ่งขึ้นตรวจสอบว่ามีอยู่หรือไม่ ทันทีที่พบหมายเลขที่ต้องการ การค้นหาจะต้องหยุดลง และรายการ “พบหมายเลขที่ต้องการแล้ว!” ควรปรากฏในคอนโซล ดัชนีในอาร์เรย์ = ....” คุณจะแก้ไขปัญหาดังกล่าวอย่างไร? วิธีแก้ปัญหานี้ชัดเจน: คุณต้องวนซ้ำองค์ประกอบอาร์เรย์ทีละรายการ โดยเริ่มจากองค์ประกอบแรก (หรือสุดท้าย) และตรวจสอบว่าหมายเลขปัจจุบันตรงกับหมายเลขที่ต้องการหรือไม่ ดังนั้นจำนวนการกระทำจึงขึ้นอยู่กับจำนวนองค์ประกอบในอาร์เรย์โดยตรง หากเรามีตัวเลข 100 ตัว เราก็ต้องไปที่องค์ประกอบถัดไป 100 ครั้ง และตรวจสอบตัวเลขว่าตรงกัน 100 ครั้ง หากมี 1,000 หมายเลข ก็จะมีขั้นตอนการตรวจสอบ 1,000 ขั้นตอน นี่คือความซับซ้อนเชิงเส้นอย่างเห็นได้ชัดO(N ) ตอนนี้เราจะเพิ่มคำอธิบายหนึ่งข้อให้กับตัวอย่างของเรา: อาร์เรย์ที่คุณต้องการค้นหาตัวเลขจะเรียงลำดับจากน้อยไปหามาก สิ่งนี้เปลี่ยนแปลงอะไรสำหรับงานของเราหรือไม่? เรายังสามารถค้นหาหมายเลขที่ต้องการได้โดยใช้กำลังดุร้าย แต่เราสามารถใช้ อัลกอริธึมการค้นหาไบนารี่ ที่รู้จักกันดี แทนได้ ในแถวบนสุดของรูปภาพ เราเห็นอาร์เรย์ที่เรียงลำดับแล้ว ในนั้นเราจำเป็นต้องค้นหาหมายเลข 23 แทนที่จะวนซ้ำตัวเลข เราเพียงแบ่งอาร์เรย์ออกเป็น 2 ส่วนและตรวจสอบตัวเลขเฉลี่ยในอาร์เรย์ เราค้นหาหมายเลขที่อยู่ในเซลล์ 4 และตรวจสอบ (แถวที่สองในภาพ) หมายเลขนี้คือ 16 และเรากำลังมองหา 23 หมายเลขปัจจุบันน้อยกว่า สิ่งนี้หมายความว่า? ไม่จำเป็นต้องตรวจสอบหมายเลขก่อนหน้า ทั้งหมด(ซึ่งอยู่จนถึงหมายเลข 16) : ตัวเลขเหล่านั้นจะน้อยกว่าหมายเลขที่เรากำลังมองหาอย่างแน่นอน เนื่องจากอาร์เรย์ของเราถูกจัดเรียงแล้ว! เรามาค้นหาองค์ประกอบทั้ง 5 ที่เหลือต่อไป ใส่ใจ:เราทำการตรวจสอบเพียงครั้งเดียว แต่เราได้กำจัดตัวเลือกที่เป็นไปได้ไปครึ่งหนึ่งแล้ว เราเหลือเพียง 5 องค์ประกอบเท่านั้น เราจะทำซ้ำขั้นตอนของเรา - แบ่งอาร์เรย์ที่เหลือด้วย 2 อีกครั้งแล้วนำองค์ประกอบตรงกลางอีกครั้ง (บรรทัดที่ 3 ในรูป) หมายเลขนี้คือ 56 และมากกว่าหมายเลขที่เรากำลังมองหา สิ่งนี้หมายความว่า? ให้เราละทิ้งตัวเลือกอีก 3 ตัว - หมายเลข 56 และตัวเลขสองตัวหลังจากนั้น (มากกว่า 23 แน่นอนเนื่องจากอาร์เรย์ถูกจัดเรียง) เราเหลือตัวเลขที่ต้องตรวจสอบเพียง 2 ตัว (แถวสุดท้ายในรูป) - ตัวเลขที่มีดัชนีอาร์เรย์ 5 และ 6 เราตรวจสอบตัวแรกและนี่คือสิ่งที่เรากำลังมองหา - หมายเลข 23! ดัชนีของมัน = 5! ลองดูผลลัพธ์ของอัลกอริทึมของเรา แล้วเราจะเข้าใจความซับซ้อนของมัน (ยังไงก็ตาม ตอนนี้คุณเข้าใจแล้วว่าทำไมจึงเรียกว่าไบนารี่: สาระสำคัญของมันคือการแบ่งข้อมูลด้วย 2 อย่างต่อเนื่อง) ผลลัพธ์ที่ได้ก็น่าประทับใจ! หากเราค้นหาตัวเลขที่ต้องการโดยใช้การค้นหาเชิงเส้น เราจะต้องตรวจสอบ 10 ครั้ง แต่ด้วยการค้นหาแบบไบนารีเราทำได้ใน 3 ครั้ง! ในกรณีที่เลวร้ายที่สุด ก็จะมี 4 รายการ หากในขั้นตอนสุดท้ายหมายเลขที่เราต้องการกลายเป็นหมายเลขที่สอง ไม่ใช่หมายเลขแรก แล้วความซับซ้อนของมันล่ะ? นี่เป็นจุดที่น่าสนใจมาก :) อัลกอริธึมการค้นหาแบบไบนารีขึ้นอยู่กับจำนวนองค์ประกอบในอาร์เรย์น้อยกว่าอัลกอริธึมการค้นหาเชิงเส้น (นั่นคือ การแจงนับอย่างง่าย) ด้วย องค์ประกอบ 10รายการในอาร์เรย์ การค้นหาเชิงเส้นจะต้องมีการตรวจสอบสูงสุด 10 ครั้ง และการค้นหาแบบไบนารีจะต้องมีการตรวจสอบสูงสุด 4 ครั้ง ความแตกต่างคือ 2.5 เท่า แต่สำหรับอาร์เรย์ที่มีองค์ประกอบ 1,000 รายการการค้นหาเชิงเส้นจะต้องมีการตรวจสอบ 1,000 ครั้ง และการค้นหาแบบไบนารี่ต้องการเพียง 10 เท่านั้น ! ความแตกต่างมีอยู่แล้ว 100 เท่า! ใส่ใจ:จำนวนองค์ประกอบในอาร์เรย์เพิ่มขึ้น 100 เท่า (จาก 10 เป็น 1,000) และจำนวนการตรวจสอบที่จำเป็นสำหรับการค้นหาแบบไบนารีเพิ่มขึ้นเพียง 2.5 เท่า - จาก 4 เป็น 10 ถ้าเราไปถึง 10,000 องค์ประกอบความแตกต่างจะยิ่งน่าประทับใจยิ่งขึ้น: 10,000 ตรวจสอบการค้นหาเชิงเส้น และ การตรวจสอบ ไบนารีทั้งหมด 14 รายการ และอีกครั้ง: จำนวนองค์ประกอบเพิ่มขึ้น 1,000 เท่า (จาก 10 เป็น 10,000) แต่จำนวนการตรวจสอบเพิ่มขึ้นเพียง 3.5 เท่า (จาก 4 เป็น 14) ความซับซ้อนของอัลกอริทึมการค้นหาแบบไบนารีคือลอการิทึมหรือในรูปแบบ Big-O คือO(log n ) ทำไมจึงเรียกอย่างนั้น? ลอการิทึมคือค่าผกผันของการยกกำลัง ลอการิทึมไบนารีใช้ในการคำนวณกำลังของ 2 ตัวอย่างเช่น เรามี 10,000 องค์ประกอบที่เราต้องค้นหาโดยใช้การค้นหาแบบไบนารี ตอนนี้คุณมีภาพต่อหน้าต่อตาคุณแล้ว และคุณรู้ว่าสิ่งนี้ต้องมีการตรวจสอบสูงสุด 14 ครั้ง แต่จะเกิดอะไรขึ้นหากไม่มีภาพต่อหน้าต่อตาคุณและคุณต้องนับจำนวนเช็คที่จำเป็นอย่างแน่นอน? ก็เพียงพอแล้วที่จะตอบคำถามง่ายๆ: ควรเพิ่มเลข 2 ให้เป็นกำลังเท่าใดจึงจะได้ผลลัพธ์เป็น >= จำนวนองค์ประกอบที่ถูกตรวจสอบ? สำหรับ 10,000 จะเป็นยกกำลังที่ 14 2 กำลัง 13 นั้นน้อยเกินไป (8192) แต่2 กำลัง 14 = 16384ตัวเลขนี้เป็นไปตามเงื่อนไขของเรา (คือ >= จำนวนองค์ประกอบในอาร์เรย์) เราพบลอการิทึม - 14 นั่นคือจำนวนเช็คที่เราต้องการ! :) อัลกอริทึมและความซับซ้อนเป็นหัวข้อที่กว้างใหญ่เกินกว่าจะรวมไว้ในการบรรยายครั้งเดียว แต่การรู้เป็นสิ่งสำคัญมาก ในการสัมภาษณ์หลายครั้ง คุณจะพบปัญหาอัลกอริทึม สำหรับทฤษฎี ฉันสามารถแนะนำหนังสือหลายเล่มให้คุณได้ จุดเริ่มต้นที่ดีคือ " Grocking Algorithms " แม้ว่าตัวอย่างในหนังสือเล่มนี้จะเขียนด้วยภาษา Python แต่ภาษาและตัวอย่างของหนังสือก็เรียบง่ายมาก ตัวเลือกที่ดีที่สุดสำหรับผู้เริ่มต้นและยังมีปริมาณน้อยอีกด้วย การอ่านที่จริงจังยิ่งขึ้น: หนังสือของRobert LaforetและRobert Sedgwick ทั้งสองเขียนด้วยภาษา Java ซึ่งจะทำให้การเรียนรู้ง่ายขึ้นเล็กน้อยสำหรับคุณ ท้ายที่สุดคุณค่อนข้างคุ้นเคยกับภาษานี้! :) สำหรับนักเรียนที่มีพื้นฐานทางคณิตศาสตร์ ที่ดี ตัวเลือกที่ดีที่สุดคือหนังสือของ Thomas Corman แต่คุณจะไม่พอใจกับแค่ทฤษฎี! “Know” != “be can” คุณสามารถฝึกแก้ปัญหา Algorithm บนHackerRankและLeetcodeได้ ปัญหาจากที่นั่นมักจะใช้แม้ในระหว่างการสัมภาษณ์ที่ Google และ Facebook ดังนั้นคุณจะไม่เบื่ออย่างแน่นอน :) เพื่อเสริมเนื้อหาการบรรยายฉันขอแนะนำให้คุณดูวิดีโอที่ยอดเยี่ยมเกี่ยวกับ Big-Oบน YouTube พบกันใหม่ในการบรรยายครั้งต่อไป! :)