อัลกอริทึมสำหรับ Dummies Cheat Sheet

อัลกอริทึมสำหรับ Dummies Cheat Sheet - Dummies

โดย John Paul Mueller, Luca Massaron

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

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

การค้นหาอัลกอริทึมที่คุณต้องการ

ตารางต่อไปนี้อธิบายอัลกอริทึมและประเภทอัลกอริทึมที่คุณอาจพบว่ามีประโยชน์สำหรับการวิเคราะห์ข้อมูลประเภทต่างๆ

คำอธิบาย ลิงก์ที่เป็นประโยชน์
A * ค้นหา อัลกอริทึมจะติดตามค่าโหนดเมื่อสำรวจโดยใช้ สมการ: f (n) = g (n) + h (n) โดยที่:

คือโหนดที่ระบุ g (n)

เป็นค่าใช้จ่ายในการเข้าถึงโหนดจนถึง h (n) เป็นค่าใช้จ่ายโดยประมาณที่จะถึง เป้าหมายจากโหนด

f (n)

คือค่าใช้จ่ายโดยประมาณของเส้นทางจาก n ถึงเป้าหมาย แนวคิดคือการค้นหาเส้นทางที่มีแนวโน้มมากที่สุดก่อนและหลีกเลี่ยงเส้นทางที่มีราคาแพง

Standford edu

Balanced Tree
ต้นไม้ชนิดหนึ่งที่รักษาโครงสร้างที่สมดุลผ่านการปรับโครงสร้างองค์กรเพื่อให้สามารถลดเวลาในการเข้าถึงได้ จำนวนองค์ประกอบด้านซ้ายแตกต่างจากตัวเลขด้านขวาโดยส่วนใหญ่ Webdocs การค้นหาแบบสองทิศทาง
เทคนิคนี้ค้นหาพร้อมกันจากโหนดรากและโหนดปลายทางจนกระทั่งทั้งสองเส้นทางการค้นหาตรงกลาง ข้อได้เปรียบของแนวทางนี้ก็คือเวลาที่มีประสิทธิภาพเพราะพบว่าโซลูชันนี้เร็วกว่าโซลูชันอื่น ๆ ของ Brute-Force นอกจากนี้ยังใช้หน่วยความจำได้อย่างมีประสิทธิภาพกว่าวิธีอื่น ๆ และมักจะหาทางออก ข้อเสียเปรียบหลักคือความซับซ้อนของการใช้งาน การวางแผน cs Binary Tree
ต้นไม้ไบนารี นี่คือชนิดของโหนดที่มีโหนดที่เชื่อมต่อกับโหนดอื่น (โหนดโหนด) หนึ่งหรือสองโหนด แต่ละโหนดกำหนดองค์ประกอบ 3 อย่างที่ต้องประกอบด้วยเพื่อจัดเตรียมการเชื่อมต่อและจัดเก็บข้อมูล: การจัดเก็บข้อมูลการเชื่อมต่อด้านซ้ายและการเชื่อมต่อที่เหมาะสม cs มหาวิทยาลัยเชียงใหม่ edu
การค้นหาแบบ Breadth-First เทคนิคนี้เริ่มต้นที่โหนดรากสำรวจแต่ละโหนดย่อยก่อนแล้วจึงเลื่อนลงไปที่ระดับถัดไป มันดำเนินไปตามระดับโดยระดับจนกว่าจะพบทางออก ข้อเสียของอัลกอริทึมนี้คือต้องเก็บทุกโหนดในหน่วยความจำซึ่งหมายความว่าจะใช้หน่วยความจำจำนวนมากสำหรับโหนดจำนวนมาก เทคนิคนี้สามารถตรวจสอบโหนดที่ซ้ำกันซึ่งจะช่วยประหยัดเวลาและมักจะมาพร้อมกับโซลูชัน Khan Academcy
Brute Force นี่คือเทคนิคในการแก้ปัญหาที่ผู้ใช้พยายามแก้ไขทุกครั้งเพื่อหาแนวทางแก้ปัญหาที่ดีที่สุด เทคนิค Brute Force ใช้เป็นแนวทางในการแก้ปัญหาที่ดีที่สุดเมื่อมีอยู่ แต่ต้องเสียเวลาในการดำเนินการให้คนส่วนใหญ่หลีกเลี่ยง Igm
การค้นหาความชัดลึก เทคนิคนี้เริ่มต้นที่โหนดรากและสำรวจชุดโหนดย่อยที่เชื่อมต่อกันจนกว่าจะถึงโหนดใบ ดำเนินการสาขาโดยสาขาจนกว่าจะพบทางออก ข้อเสียของอัลกอริธึมนี้คือไม่สามารถตรวจสอบโหนดที่ซ้ำกันได้ซึ่งหมายความว่าสามารถข้ามเส้นทางโหนดเดียวกันได้มากกว่าหนึ่งครั้ง ในความเป็นจริงอัลกอริทึมนี้อาจไม่พบทางออกเลยซึ่งหมายความว่าคุณต้องกำหนดจุดตัดเพื่อไม่ให้เกิดอัลกอริธึมจากการค้นหาแบบอนันต์ ข้อดีของวิธีนี้ก็คือประสิทธิภาพของหน่วยความจำ Hacker Earth
แบ่งและพิชิต นี่เป็นเทคนิคในการแก้ปัญหาซึ่งปัญหาจะถูกแบ่งออกเป็นชิ้นเล็กที่สุดเท่าที่จะทำได้และแก้ไขได้โดยใช้วิธีที่ง่ายที่สุด เทคนิคนี้ช่วยประหยัดเวลาและทรัพยากรได้มากเมื่อเทียบกับวิธีการอื่น ๆ เช่นกำลังเดรัจฉาน อย่างไรก็ตามไม่รับประกันผลที่ดีที่สุดเสมอไป Khan Academy
Dijikstra นี่คืออัลกอริทึมที่ใช้ในการค้นหาเส้นทางที่สั้นที่สุดในกราฟที่มีน้ำหนักถ่วงน้ำหนัก (มีน้ำหนักบวก) Geeks for Geeks
กราฟ กราฟคือส่วนขยายของต้นไม้ เช่นเดียวกับต้นไม้คุณมีโหนดที่เชื่อมต่อกันเพื่อสร้างความสัมพันธ์ อย่างไรก็ตามไม่เหมือนต้นไม้ไบนารีกราฟอาจมีการเชื่อมต่อมากกว่าหนึ่งหรือสองรายการ ในความเป็นจริงโหนดกราฟมักมีการเชื่อมต่อมากมาย คุณจะเห็นกราฟที่ใช้ในสถานที่ต่างๆเช่นแผนที่ GPS และสถานที่อื่น ๆ ทั้งหมดซึ่งวิธีการบนลงล่างของต้นไม้จะไม่ทำงาน อัลกอริธึมความโลภ
เทคนิคหนึ่งของการแก้ปัญหาซึ่งในทางออกนั้นจะต้องอาศัยคำตอบที่ดีที่สุดสำหรับทุกขั้นตอนของกระบวนการแก้ปัญหา อัลกอริธึมโลภมักทำสมมติฐานสองข้อ:

สามารถเลือกทางเลือกที่เหมาะสมได้ในขั้นตอนเดียวเท่านั้น

โดยการเลือกการเลือกที่ดีที่สุดในแต่ละขั้นตอนการหาทางออกที่ดีที่สุดสำหรับปัญหาโดยรวมนั้นเป็นไปได้

การค้นหาที่ดีที่สุดครั้งแรก (BASE)
อัลกอริธึมเลือกเส้นทางที่ใกล้เคียงกับเป้าหมายมากที่สุดโดยใช้สมการดังนี้ f (n) = h ( n) อัลกอริธึมเฉพาะนี้สามารถหาคำตอบได้อย่างรวดเร็ว แต่ยังสามารถติดค้างอยู่ในลูปได้ดังนั้นคนจำนวนมากจึงไม่คิดว่าวิธีที่ดีที่สุดในการหาโซลูชัน Centurion2 Hashing
นี่เป็นวิธีการทำนายตำแหน่งของข้อมูลบางรายการในโครงสร้างข้อมูล (ไม่ว่าจะเป็นโครงสร้างใดก็ตาม) ก่อนที่จะหาข้อมูลจริง วิธีนี้อาศัยการใช้คีย์ที่วางไว้ในดัชนี ฟังก์ชันแฮชจะเปลี่ยนคีย์เป็นค่าตัวเลขซึ่งอัลกอริทึมจะวางลงในตารางแฮช ตารางแฮชให้ความหมายในการสร้างดัชนีที่ชี้ไปยังองค์ประกอบในโครงสร้างข้อมูลเพื่อให้อัลกอริทึมสามารถทำนายตำแหน่งของข้อมูลได้อย่างง่ายดาย บทแนะนำ Heap
นี่เป็นโครงสร้างที่ซับซ้อนซึ่งสามารถแทรกข้อมูลลงในโครงสร้างของต้นไม้ได้ การใช้การแทรกข้อมูลทำให้การเรียงลำดับทำได้เร็วขึ้น คุณสามารถจำแนกต้นไม้เหล่านี้เป็นกองสูงสุดและกอง heaps ได้ขึ้นอยู่กับความสามารถของต้นไม้ในการระบุค่าสูงสุดหรือต่ำสุดในต้นไม้ได้ทันที บทแนะนำ Heuristics
นี่เป็นเทคนิคในการแก้ปัญหาที่อาศัยการค้นพบตัวเองและสร้างผลลัพธ์ที่มีประโยชน์พอสมควร (ไม่จำเป็นต้องดีที่สุด แต่ดีพอ) เพื่อแก้ปัญหาได้ดีพอที่จะเป็นทางเลือกที่ดีกว่า ' t จำเป็น การค้นพบตัวเองเป็นกระบวนการที่ช่วยให้อัลกอริทึมสามารถแสดงเส้นทางที่เป็นประโยชน์สำหรับโซลูชัน (แต่คุณต้องอาศัยสัญชาตญาณของมนุษย์และเข้าใจว่าโซลูชันนี้เหมาะสมหรือไม่) ภาคตะวันตกเฉียงเหนือ edu MapReduce
MapReduce นี่คือกรอบการทำงานของอัลกอริทึมที่ทำงานโดยใช้การคำนวณแบบขนาน (ใช้คอมพิวเตอร์หลายเครื่องที่เชื่อมต่อกันในเครือข่าย) ทำให้อัลกอริทึมสามารถแก้ปัญหาได้เร็วขึ้น Hadoop Apache
Mergesort Mergesort เป็นโซลูชันการเปรียบเทียบข้อมูลที่ใช้โดยทั่วไปสำหรับการเปรียบเทียบ ขึ้นอยู่กับวิธีแบ่งแยกและพิชิตในการปฏิบัติงาน Geeks for Geeks
Nash Equilibrium นี่คือทฤษฎีเกมที่ผู้เล่นคนอื่น ๆ รู้จักกลยุทธ์ดุลยภาพสำหรับผู้เล่นคนอื่น ๆ ดังนั้นจึงไม่มีใครสามารถทำอะไรได้โดยการเปลี่ยนกลยุทธ์ส่วนบุคคลของเขาหรือเธอ ทฤษฎีนี้เห็นการใช้งานในสถานการณ์ที่ไม่เป็นมิตรซึ่งผู้เล่นต้องคำนึงถึงการตัดสินใจของผู้เล่นรายอื่น ๆ เพื่อที่จะชนะเกม Khan Academy
PageRank PageRank คืออัลกอริทึมสำหรับการวัดความสำคัญของโหนดในกราฟ อัลกอริทึมนี้เป็นรากฐานของอัลกอริทึมหลักของ Google เพื่อเปิดการค้นหาที่เกี่ยวข้องกับผู้ใช้ พรินซ์ตัน edu
ค้นหา Heuristic บริสุทธิ์ อัลกอริทึมนี้จะขยายโหนดตามลำดับค่าใช้จ่าย จะมีสองรายการ รายการที่ปิดไว้มีโหนดที่ได้สำรวจไปแล้วและรายการที่เปิดจะมีโหนดที่ต้องสำรวจ ในขั้นตอนแต่ละครั้งอัลกอริทึมจะขยายโหนดที่มีต้นทุนต่ำที่สุด โหนดย่อยทั้งหมดจะอยู่ในรายการที่ถูกปิดและคำนวณค่าใช้จ่ายโหนดย่อยของแต่ละโหนด อัลกอริทึมจะส่งโหนดย่อยที่มีต้นทุนต่ำกลับไปที่รายการเปิดและลบโหนดย่อยด้วยค่าใช้จ่ายสูง ดังนั้นอัลกอริทึมจะทำการค้นหาโซลูชันโดยใช้ค่าใช้จ่ายที่ชาญฉลาด World of Computing
Quicksort นี่คือกลยุทธ์การจัดเรียงข้อมูลทั่วไปที่ใช้อาร์เรย์แบ่งพาร์ติชันของข้อมูลลงในอาร์เรย์เล็ก ๆขึ้นอยู่กับวิธีแบ่งแยกและพิชิตในการปฏิบัติงาน บทแนะนำ
ต้นไม้ที่ไม่สมดุลย์ นี่คือต้นไม้ที่วางรายการข้อมูลใหม่ ๆ เมื่อจำเป็นในต้นไม้โดยไม่คำนึงถึงความสมดุล วิธีการเพิ่มรายการนี้ทำให้การสร้างโครงสร้างทำได้เร็วขึ้น แต่ลดความเร็วในการเข้าถึงเมื่อค้นหาหรือเรียงลำดับ Quora

อัลกอริทึมที่แตกต่างจากโครงสร้างทางคณิตศาสตร์อื่น ๆ

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

โครงสร้าง คำอธิบาย
สมการ ตัวเลขและสัญลักษณที่เมื่อถายโดยรวมแลวเทากับคาเฉพาะ สมการเสมอประกอบด้วยเครื่องหมายเท่ากับเพื่อให้คุณทราบว่าตัวเลขและสัญลักษณ์แสดงค่าที่ระบุในอีกด้านหนึ่งของเครื่องหมายเท่ากับ สมการส่วนใหญ่ประกอบด้วยข้อมูลตัวแปรที่นำเสนอเป็นสัญลักษณ์ แต่ไม่จำเป็นต้องใช้ตัวแปร
สูตร การรวมกันของตัวเลขและสัญลักษณ์ที่ใช้เพื่อแสดงข้อมูลหรือแนวคิดต่างๆ สูตรปกติจะนำเสนอแนวความคิดทางคณิตศาสตร์หรือตรรกะเช่นกำหนดตัวหารร่วมที่ยิ่งใหญ่ที่สุด (GCD) ของสองจำนวนเต็ม (วิดีโอที่ Khan Academy บอกว่าการทำงานนี้เป็นอย่างไร) โดยทั่วไปสูตรแสดงความสัมพันธ์ระหว่างตัวแปรสองตัวหรือมากกว่า คนส่วนใหญ่เห็นสูตรเป็นสมการชนิดพิเศษ
อัลกอริทึม ลำดับขั้นตอนที่ใช้ในการแก้ปัญหา ลำดับแสดงวิธีที่ไม่ซ้ำกันในการแก้ไขปัญหาด้วยการให้โซลูชันเฉพาะ อัลกอริทึมไม่จำเป็นต้องแสดงถึงแนวความคิดทางคณิตศาสตร์หรือตรรกะแม้ว่างานนำเสนอในหนังสือเล่มนี้มักจะตกอยู่ในหมวดหมู่นั้นเนื่องจากคนส่วนใหญ่ใช้อัลกอริทึมในลักษณะนี้ บางสูตรพิเศษเป็นอัลกอริทึมเช่นสูตรสมการกำลังสอง สำหรับขั้นตอนการแสดงอัลกอริทึมจะต้องมีดังต่อไปนี้

Finite: อัลกอริทึมต้องแก้ไขปัญหา

ความละเอียด: ชุดของขั้นตอนต้องเป็นไปอย่างแม่นยำและนำเสนอขั้นตอนที่เข้าใจได้โดยเฉพาะอย่างยิ่งทางคอมพิวเตอร์ซึ่งจะต้องสามารถสร้างอัลกอริทึมที่ใช้งานได้

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

วิธีการใช้อัลกอริธึมที่น่าตื่นตาตื่นใจ

คนใช้อัลกอริทึมอยู่ตลอดเวลา ตัวอย่างเช่นการทำขนมปังปิ้งเป็นตัวอย่างของอัลกอริทึมตามที่ได้อธิบายไว้ในโพสต์บล็อกนี้ การทำขนมปังปิ้งไม่ใช่อัลกอริธึมที่น่าอัศจรรย์ แต่ในตารางต่อไปนี้ซึ่งใช้คอมพิวเตอร์ในการดำเนินการคือ

งาน ทำไมมันถึงน่าอัศจรรย์
การเข้ารหัสลับ การรักษาข้อมูลให้ปลอดภัยเป็นการต่อสู้อย่างต่อเนื่องกับแฮกเกอร์ที่โจมตีแหล่งข้อมูลอย่างต่อเนื่อง อัลกอริธึมช่วยให้คุณสามารถวิเคราะห์ข้อมูลใส่ลงในฟอร์มอื่น ๆ แล้วส่งกลับไปยังรูปแบบเดิมในภายหลัง
การวิเคราะห์กราฟ ความสามารถในการตัดสินใจเกี่ยวกับเส้นที่สั้นที่สุดระหว่างจุดสองจุดจะพบการใช้งานทุกประเภท ตัวอย่างเช่นในปัญหาเกี่ยวกับการกำหนดเส้นทาง GPS ของคุณจะไม่สามารถทำงานได้หากไม่มีอัลกอริธึมเฉพาะนี้เนื่องจากไม่สามารถนำคุณไปตามถนนในเมืองโดยใช้เส้นทางที่สั้นที่สุดจากจุด A ไปยังจุด B
การสร้างหมายเลข Pseudorandom ลองนึกภาพเล่นเกม ที่ไม่เคยแตกต่างกัน คุณเริ่มต้นที่สถานที่เดียวกันและทำตามขั้นตอนเดียวกันในลักษณะเดียวกันทุกครั้งที่คุณเล่น น่าเบื่อ! หากไม่มีความสามารถในการสร้างตัวเลขสุ่มที่ดูเหมือนว่างานคอมพิวเตอร์จำนวนมากจะไม่มีจุดหมายหรือเป็นไปไม่ได้
การจัดตารางเวลา การใช้ทรัพยากรอย่างเป็นธรรมกับทุกคนที่เกี่ยวข้องเป็นอีกวิธีหนึ่งที่อัลกอริทึมจะทำให้การแสดงตนเป็นที่รู้จักอย่างใหญ่หลวง ตัวอย่างเช่นไฟจับเวลาที่ทางแยกไม่ได้เป็นอุปกรณ์ง่ายๆที่นับวินาทีระหว่างการเปลี่ยนแปลงของแสง อุปกรณ์ที่ทันสมัยคำนึงถึงปัญหาทุกประเภทเช่นเวลากลางวันสภาพอากาศและการไหลของการจราจร การจัดตารางเวลามีหลายรูปแบบอย่างไรก็ตาม พิจารณาว่าคอมพิวเตอร์ของคุณใช้งานหลายงานพร้อม ๆ กันได้อย่างไร หากไม่มีอัลกอริทึมการตั้งเวลาระบบปฏิบัติการอาจคว้าทรัพยากรทั้งหมดที่มีอยู่และทำให้แอพพลิเคชันของคุณไม่ทำงานที่เป็นประโยชน์
การค้นหา การค้นหาข้อมูลหรือยืนยันว่าข้อมูลที่คุณเห็นเป็นข้อมูลที่คุณต้องการเป็นสิ่งที่จำเป็น หากไม่มีความสามารถนี้งานหลายอย่างที่คุณทำแบบออนไลน์จะไม่สามารถทำได้เช่นการค้นหาเว็บไซต์บนอินเทอร์เน็ตที่ขายหม้อกาแฟที่สมบูรณ์แบบสำหรับออฟฟิศของคุณ
การเรียงลำดับ การกำหนดลำดับที่จะนำเสนอข้อมูลมีความสำคัญเนื่องจากคนส่วนใหญ่ในปัจจุบันต้องทนทุกข์ทรมานจากการมีข้อมูลมากเกินไปและต้องลดการบุกรุกข้อมูล ลองนึกภาพไปที่ Amazon แล้วพบว่ามีหม้อกาแฟมากกว่าหนึ่งพันเครื่องสำหรับขาย แต่ยังไม่สามารถจัดเรียงตามราคาหรือการทบทวนในเชิงบวกได้มากที่สุด นอกจากนี้อัลกอริทึมที่ซับซ้อนหลายแห่งยังต้องการข้อมูลที่ถูกต้องในการทำงานอย่างเหมาะสมเพื่อให้การเรียงลำดับเป็นสิ่งจำเป็นสำหรับการแก้ปัญหาได้มากขึ้น
การแปลง การแปลงข้อมูลประเภทหนึ่งไปเป็นข้อมูลชนิดอื่นมีความสำคัญต่อการทำความเข้าใจและใช้ข้อมูลอย่างมีประสิทธิภาพ ตัวอย่างเช่นคุณอาจเข้าใจน้ำหนักของจักรวรรดิได้ดี แต่แหล่งที่มาทั้งหมดของคุณใช้ระบบเมตริก การแปลงระหว่างระบบทั้งสองช่วยให้คุณเข้าใจข้อมูล ในทำนองเดียวกัน Fast Fourier Transform (FFT) จะแปลงสัญญาณระหว่างโดเมนเวลาและโดเมนความถี่ทำให้สิ่งต่างๆเช่นเราเตอร์ WiFi ทำงานได้

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

คุณรู้อยู่แล้วว่าอัลกอริทึมมีความซับซ้อน อย่างไรก็ตามคุณจำเป็นต้องรู้วิธีการซับซ้อนของอัลกอริทึมเนื่องจากยิ่งซับซ้อนมากขึ้นเท่าใดก็ยิ่งใช้เวลานานเท่าใดก็ได้ ตารางต่อไปนี้ช่วยให้คุณเข้าใจระดับความซับซ้อนต่างๆที่แสดงตามลำดับเวลาในการทำงาน (จากที่เร็วที่สุดไปช้าที่สุด)

ความซับซ้อน คำอธิบาย
ความซับซ้อนคงที่ O (1) ให้เวลาในการดำเนินการที่ไม่แน่นอนไม่ว่าคุณจะใส่ข้อมูลเท่าไร การป้อนข้อมูลแต่ละครั้งต้องใช้เวลาดำเนินการหนึ่งหน่วย
ความซับซ้อนลอการิทึม O (log n) จำนวนการดำเนินงานเติบโตที่อัตราที่ช้ากว่าข้อมูลที่ป้อนทำให้อัลกอริทึมมีประสิทธิภาพน้อยกว่าเมื่อใช้อินพุตขนาดเล็กและมีประสิทธิภาพมากขึ้นกับระบบที่มีขนาดใหญ่ อัลกอริธึมทั่วไปของคลาสนี้คือการค้นหาไบนารี
ความซับซ้อนเชิงเส้น O (n) การดำเนินงานจะเติบโตไปพร้อมกับการป้อนข้อมูลในอัตราส่วน 1: 1 อัลกอริธึมทั่วไปคือการทำซ้ำเมื่อคุณสแกนอินพุทเพียงครั้งเดียวและใช้การดำเนินงานกับแต่ละองค์ประกอบของข้อมูล
ความซับซ้อนเชิง Linearithmic O (n log n) ความซับซ้อนเป็นส่วนผสมระหว่างความซับซ้อนลอการิทึมและเชิงเส้น เป็นปกติของอัลกอริทึมสมาร์ทบางตัวที่ใช้ในการสั่งซื้อข้อมูลเช่น Mergesortsort, Heapsort และ Quicksort
ความซับซ้อนของรูปสี่เหลี่ยมจัตุรัส O (n 2 ) การดำเนินการจะเติบโตเป็นรูปสี่เหลี่ยมจัตุรัสของจำนวนอินพุท เมื่อคุณมีการย้ำอีกครั้งภายในการทำซ้ำอื่น (เรียกว่าการซ้อนซ้ำ ๆ ในวิทยาการคอมพิวเตอร์) คุณมีความซับซ้อนแบบสมการกำลังสอง ตัวอย่างเช่นคุณมีรายชื่อและเพื่อหาคนที่คล้ายกันมากที่สุดคุณจะเปรียบเทียบชื่อแต่ละชื่อกับชื่ออื่น ๆ ทั้งหมด อัลกอริทึมการสั่งซื้อที่มีประสิทธิภาพน้อยกว่ามีความซับซ้อนเช่นการจัดเรียงแบบฟองสบู่การเรียงลำดับการเลือกและการจัดเรียงการแทรก ระดับความซับซ้อนนี้หมายความว่าอัลกอริทึมของคุณอาจทำงานเป็นเวลาหลายชั่วโมงหรือหลายวันก่อนที่จะถึงทางออก
ความซับซ้อนของลูกบาศก์ O (n 3 ) การดำเนินงานจะเติบโตได้เร็วกว่าความซับซ้อนแบบสองส่วนเนื่องจากตอนนี้คุณมีการซ้อนหลายครั้ง เมื่ออัลกอริทึมมีลำดับความซับซ้อนนี้และคุณต้องประมวลผลข้อมูลจำนวนเล็กน้อย (100, 000 องค์ประกอบ) อัลกอริทึมของคุณอาจทำงานเป็นเวลาหลายปี เมื่อคุณมีจำนวนของการดำเนินการที่เป็นพลังงานของอินพุทเป็นเรื่องปกติที่จะอ้างถึงอัลกอริทึมที่ทำงานในเวลาพหุนาม
ความซับซ้อนเชิงซ้อน O (2 n ) อัลกอริทึมจะใช้เวลาสองถึงสามครั้งของการดำเนินงานก่อนหน้าสำหรับทุกๆองค์ประกอบใหม่ที่เพิ่มเข้าไป เมื่ออัลกอริทึมมีความซับซ้อนเช่นนี้แม้แต่ปัญหาเล็ก ๆ อาจใช้เวลาตลอดไป อัลกอริธึมจำนวนมากที่ทำการค้นหาอย่างละเอียดถี่ถ้วนมีความซับซ้อนที่อธิบาย อย่างไรก็ตามตัวอย่างคลาสสิกสำหรับระดับความซับซ้อนนี้คือการคำนวณตัวเลข Fibonacci
Factorial complexity O (n!) อัลกอริทึมนี้เป็นภาพลวงตาของความซับซ้อนเนื่องจากมีการผสมผสานระหว่างองค์ประกอบต่างๆเป็นจำนวนมาก ลองนึกภาพ: ถ้าข้อมูลของคุณคือ 100 วัตถุและการดำเนินการในคอมพิวเตอร์ของคุณจะใช้เวลาประมาณ 10 -6 999 วินาที (ความเร็วที่เหมาะสมสำหรับคอมพิวเตอร์ทุกเครื่องทุกวันนี้) คุณจะต้องใช้เวลาประมาณ 10 ปี 140 เพื่อให้งานเสร็จสมบูรณ์ (เป็นไปไม่ได้ที่เวลาเพราะอายุของจักรวาลประมาณ 10 ปี 14 ) ปัญหาความซับซ้อนที่มีชื่อเสียงคือปัญหาพนักงานขายที่เดินทางซึ่งพนักงานขายต้องหาเส้นทางที่สั้นที่สุดสำหรับการเยี่ยมชมเมืองต่างๆและกลับมาที่เมืองเริ่มต้น

ติดต่อเรา: [email protected]