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

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

• เสื้อผ้า
• ทำความสะอาด
• เลี้ยง

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

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

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

1. ซื้อหรือดาวน์โหลดพจนานุกรม New International ฉบับที่สามของเว็บสเตอร์ฉบับปี 1961
2. ค้นหาทุกชื่อจากรายการของเราในพจนานุกรมนี้
3. เขียนหน้าพจนานุกรมที่ชื่อนั้นลงบนกระดาษ
4. ใช้เศษกระดาษเพื่อจัดเรียงชื่อ

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

int[] numbers = new int[100];
// ...fill the array with numbers

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) คือความซับซ้อนคงที่ ทำไม โปรดทราบว่าเราใส่ตัวเลขแต่ละตัวที่จุดเริ่มต้นของรายการ นอกจากนี้ คุณจะจำได้ว่าเมื่อคุณใส่ตัวเลขลงใน a LinkedListองค์ประกอบต่างๆ จะไม่ย้ายไปไหน ลิงก์ (หรือการอ้างอิง) ได้รับการอัปเดต (หากคุณลืมว่า LinkedList ทำงานอย่างไร โปรดดูบทเรียนเก่า บทหนึ่งของเรา ) หากหมายเลขแรกในรายการของเราคือxและเราใส่หมายเลข y ที่ด้านหน้าของรายการ สิ่งที่เราต้องทำคือ:

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

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

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

อย่าตื่นตกใจ! :) หากคำว่า "ลอการิทึม" ทำให้คุณต้องการปิดบทเรียนนี้และหยุดอ่าน เพียงรอสักครู่ จะไม่มีคณิตศาสตร์บ้าๆ อยู่ที่นี่ (มีคำอธิบายมากมายในที่อื่น) และเราจะแยกแต่ละตัวอย่างออกจากกัน ลองนึกภาพว่างานของคุณคือค้นหาหมายเลขเฉพาะหนึ่งในอาร์เรย์ที่มี 100 หมายเลข อย่างแม่นยำยิ่งขึ้นคุณต้องตรวจสอบว่ามีอยู่หรือไม่ ทันทีที่พบหมายเลขที่ต้องการ การค้นหาจะสิ้นสุดลง และคุณแสดงข้อความต่อไปนี้ในคอนโซล: "พบหมายเลขที่ต้องการแล้ว! ดัชนีของมันในอาร์เรย์ = ...." คุณจะทำงานนี้ให้สำเร็จได้อย่างไร วิธีแก้ปัญหานั้นชัดเจน: คุณต้องวนซ้ำองค์ประกอบของอาร์เรย์ทีละรายการโดยเริ่มจากอันแรก (หรือจากอันสุดท้าย) และตรวจสอบว่าหมายเลขปัจจุบันตรงกับหมายเลขที่คุณต้องการหรือไม่ ดังนั้น จำนวนของการกระทำโดยตรงขึ้นอยู่กับจำนวนขององค์ประกอบในอาร์เรย์ หากเรามีตัวเลข 100 ตัว เราอาจต้องไปที่องค์ประกอบถัดไป 100 ครั้งและทำการเปรียบเทียบ 100 ครั้ง หากมีตัวเลข 1,000 ตัว ก็อาจมีการเปรียบเทียบได้ 1,000 รายการ นี่คือความซับซ้อนเชิงเส้นที่เห็นได้ชัด กล่าวคือโอ(น) . และตอนนี้เราจะเพิ่มการปรับแต่งหนึ่งอย่างให้กับตัวอย่างของเรา: อาร์เรย์ที่คุณต้องการค้นหาตัวเลขจะเรียงลำดับจากน้อยไปหามาก สิ่งนี้เปลี่ยนแปลงอะไรเกี่ยวกับงานของเราหรือไม่? เรายังคงสามารถค้นหาหมายเลขที่ต้องการได้อย่างดุร้าย แต่อีกทางหนึ่ง เราสามารถใช้อั ลก อริทึมการค้นหาแบบไบนารีที่รู้จักกันดี ในแถวบนสุดของภาพ เราเห็นอาร์เรย์ที่เรียงลำดับ เราต้องหาเลข 23 ในนั้น แทนที่จะวนซ้ำกับตัวเลข เราเพียงแค่แบ่งอาร์เรย์ออกเป็น 2 ส่วนและตรวจสอบตัวเลขตรงกลางในอาร์เรย์ ค้นหาหมายเลขที่อยู่ในเซลล์ 4 และตรวจสอบ (แถวที่สองในภาพ) หมายเลขนี้คือ 16 และเรากำลังมองหา 23 จำนวนปัจจุบันน้อยกว่าที่เรากำลังมองหา นั่นหมายความว่าอย่างไร? มันหมายความว่าไม่จำเป็นต้องตรวจสอบหมายเลขก่อนหน้าทั้งหมด (หมายเลขที่อยู่ก่อนหมายเลข 16)รับประกันว่าจะน้อยกว่าหมายเลขที่เรากำลังมองหา เพราะอาร์เรย์ของเราจัดเรียงไว้แล้ว! เราดำเนินการค้นหาต่อไปใน 5 องค์ประกอบที่เหลือ บันทึก:เราทำการเปรียบเทียบเพียงครั้งเดียว แต่เราตัดตัวเลือกที่เป็นไปได้ออกไปครึ่งหนึ่งแล้ว เราเหลือเพียง 5 องค์ประกอบเท่านั้น เราจะทำขั้นตอนก่อนหน้าซ้ำอีกครั้งโดยแบ่งครึ่ง subarray ที่เหลืออีกครั้งและเอาองค์ประกอบตรงกลางอีกครั้ง (แถวที่ 3 ในภาพ) หมายเลขคือ 56 และมีขนาดใหญ่กว่าหมายเลขที่เรากำลังค้นหา นั่นหมายความว่าอย่างไร? หมายความว่าเราได้ตัดความเป็นไปได้อีก 3 อย่างออก: หมายเลข 56 เองและตัวเลขสองตัวหลังจากนั้น (เนื่องจากรับประกันว่าจะมากกว่า 23 เนื่องจากอาร์เรย์ถูกจัดเรียง) เราเหลือเพียงแค่ 2 หมายเลขที่ต้องตรวจสอบ (แถวสุดท้ายในภาพ) — ตัวเลขที่มีดัชนีอาร์เรย์ 5 และ 6 เราตรวจสอบหมายเลขแรกและพบสิ่งที่เรากำลังมองหา — หมายเลข 23! ดัชนีของมันคือ 5! มาดูผลลัพธ์ของอัลกอริทึมกัน แล้วเราจะ จะวิเคราะห์ความซับซ้อนของมัน อย่างไรก็ตาม ตอนนี้คุณเข้าใจแล้วว่าทำไมสิ่งนี้ถึงเรียกว่าการค้นหาแบบไบนารี: มันอาศัยการแบ่งครึ่งข้อมูลซ้ำๆ ผลลัพธ์น่าประทับใจ! หากเราใช้การค้นหาเชิงเส้นเพื่อค้นหาตัวเลข เราจะต้องมีการเปรียบเทียบมากถึง 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) ความซับซ้อนของอัลกอริทึมการค้นหาแบบไบนารีคือลอการิทึมหรือถ้าเราใช้สัญกรณ์ O ขนาดใหญ่O(log n). ทำไมถึงเรียกอย่างนั้น? ลอการิทึมเป็นเหมือนสิ่งที่ตรงกันข้ามกับการยกกำลัง ลอการิทึมฐานสองคือพลังที่ต้องยกเลข 2 เพื่อให้ได้ตัวเลข ตัวอย่างเช่น เรามีองค์ประกอบ 10,000 รายการที่เราต้องค้นหาโดยใช้อัลกอริทึมการค้นหาแบบไบนารี ปัจจุบัน คุณสามารถดูตารางค่าเพื่อทราบว่าการดำเนินการนี้จะต้องมีการเปรียบเทียบสูงสุด 14 รายการ แต่ถ้าไม่มีใครให้ตารางดังกล่าวและคุณต้องคำนวณจำนวนการเปรียบเทียบสูงสุดที่แน่นอน คุณเพียงแค่ต้องตอบคำถามง่ายๆ: คุณต้องเพิ่มพลังอะไรเป็นเลข 2 เพื่อให้ผลลัพธ์มากกว่าหรือเท่ากับจำนวนองค์ประกอบที่จะตรวจสอบ สำหรับ 10,000 เป็นกำลังที่ 14 2 ยกกำลัง 13 น้อยเกินไป (8192) แต่2 ยกกำลัง 14 = 16384และจำนวนนี้เป็นไปตามเงื่อนไขของเรา (มากกว่าหรือเท่ากับจำนวนองค์ประกอบในอาร์เรย์) เราพบลอการิทึม: 14 นั่นคือจำนวนการเปรียบเทียบที่เราอาจต้องการ! :) อัลกอริทึมและความซับซ้อนของอัลกอริทึมเป็นหัวข้อที่กว้างเกินไปที่จะรวมไว้ในบทเรียนเดียว แต่การรู้ว่าสิ่งนี้สำคัญมาก: การสัมภาษณ์งานจำนวนมากจะมีคำถามเกี่ยวกับอัลกอริทึม สำหรับทฤษฎี ฉันสามารถแนะนำหนังสือบางเล่มให้คุณได้ คุณสามารถเริ่มต้นด้วย " อัลกอริทึม Grokking " ตัวอย่างในหนังสือเล่มนี้เขียนด้วยภาษา Python แต่หนังสือเล่มนี้ใช้ภาษาและตัวอย่างที่ง่ายมาก เป็นตัวเลือกที่ดีที่สุดสำหรับผู้เริ่มต้น และยิ่งไปกว่านั้น มันไม่ใหญ่มาก ในบรรดาการอ่านอย่างจริงจัง เรามีหนังสือของRobert LaforeและRobert Sedgewick. ทั้งคู่เขียนด้วย Java ซึ่งจะทำให้การเรียนรู้ของคุณง่ายขึ้นเล็กน้อย ท้ายที่สุดคุณค่อนข้างคุ้นเคยกับภาษานี้! :) สำหรับนักเรียนที่มีทักษะทางคณิตศาสตร์ที่ดี ตัวเลือกที่ดีที่สุดคือหนังสือของ Thomas Cormen แต่ทฤษฎีเพียงอย่างเดียวไม่สามารถทำให้อิ่มท้องได้! ความรู้ != ความสามารถ . คุณสามารถฝึกฝนการแก้ปัญหาเกี่ยวกับอัลกอริ ทึมบนHackerRankและLeetCode งานจากเว็บไซต์เหล่านี้มักใช้ในระหว่างการสัมภาษณ์ที่ Google และ Facebook ดังนั้นคุณจะไม่เบื่ออย่างแน่นอน :) เพื่อเสริมเนื้อหาบทเรียนนี้ ฉันขอแนะนำให้คุณดูวิดีโอที่ยอดเยี่ยมเกี่ยวกับสัญลักษณ์ O ขนาดใหญ่บน YouTube แล้วพบกันในบทเรียนต่อไป! :)