การอ้างอิงอัลกอริทึมของโปรแกรมเมอร์

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

การเขียนโปรแกรม (หรือการเขียนโค้ด / วิศวกรรมซอฟต์แวร์ หรือคำเจ๋งๆ อะไรก็ตามที่เราใช้อยู่ในปัจจุบัน) มีอัลกอริทึม (algoโดยย่อ) อยู่ในหัวใจ การดำเนินการโดยไม่มีแผนไม่ได้ใกล้เคียงกับความคาดหวังอย่างที่เราทราบ ในการเขียนโปรแกรมอัลโกคือการวางแผนของเรา

มีเว็บอ้างอิงมากมายทางออนไลน์ที่เข้าถึงสิ่งเดียวกันในรูปแบบที่แตกต่างกัน แต่ไม่มีอะไรจะดีไปกว่าการอ่านหนังสือ 📚 อย่างที่คุณอาจเห็นด้วย 😁

หนังสือแนะนำเป็นอย่างยิ่ง:

รู้เบื้องต้นเกี่ยวกับอัลกอริทึม ฉบับที่ 3 (สำนักพิมพ์ MIT)

โดย Thomas H. Cormen,
Charles E. Leiserson,
et al. | 31 ก.ค. 2552

https://www.amazon.com/Data-Structures-Thomas-H-Cormen-Algorithms/

แผนภูมิการไหล:

ผังงานคือประเภทของไดอะแกรมที่แสดงถึงเวิร์กโฟลว์หรือกระบวนการ ผังงานยังสามารถกำหนดเป็นการแสดงไดอะแกรมของอัลกอริทึม ซึ่งเป็นแนวทางทีละขั้นตอนในการแก้ปัญหา — วิกิพีเดีย

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

แผนภูมิการไหลเจ๋งมาก ใช้ draw.io
ในการแก้ปัญหา — ใช้อัลโก — เพื่อเป็นตัวแทนของอัลโก — ใช้แผนภูมิการไหล

เย็น. อยู่กับฉัน. สิ่งที่น่าสนใจข้างหน้า:

ความซับซ้อน:

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

ในอุตสาหกรรมซอฟต์แวร์ เราถือว่าความซับซ้อนเป็นมาตรการในการตัดสินใจว่าจะเลือกอัลโกหรือไม่ ความซับซ้อนอาจมี 2 ปัจจัย:

1. เวลา: ประมาณ. ระยะเวลาที่โซลูชันของคุณใช้
2. พื้นที่: ประมาณ. พื้นที่ที่โซลูชันของคุณใช้ไป

เราจะนำเสนอความซับซ้อนโดยสัมพันธ์กับ 'n' โดยที่ n คือความยาวของชุดอินพุต

การแจ้งเตือนกฎเกณฑ์ง่ายๆ 🚨

👍 เวลาเป็นสิ่งมีค่า พื้นที่สามารถซื้อได้
👍 สัญลักษณ์ Big Oh(O) คือเพื่อนของเรา
👍 คำสั่งการดำเนินการและลูปกินเวลาของคุณ
👍 การเรียกซ้ำกินเวลาของคุณ

สัญกรณ์บิ๊กโอ:

O(1): read(order of 1) เป็นสิ่งที่ดีที่สุดที่สามารถทำได้ O(n): read(order of en) หมายถึงความซับซ้อนเพิ่มขึ้นตามปัจจัยของความยาวของชุดอินพุต (เช่น n) โปรแกรมใช้เวลาส่วนใหญ่วนซ้ำ ดังนั้นดูมัน

ตัวอย่าง (ความซับซ้อนของเวลา) 🖥 ⏰

O(1): ไม่เกี่ยวข้องกับ 'n'

aka เวลาคงที่ เป้าหมายการเขียนโปรแกรม 🤞.

sum = a+b // constant time O(1)
anotherSum = (a+b) * 10000000000 // constant time O(1)
somethingElse = functionCall() // depends of function def. duh!

O(n): ตัวประกอบคงที่ของ 'n'

ลำดับของ 'n' ดีที่สุดที่คุณสามารถทำได้เกือบตลอดเวลา

for(var i=0; i<n; i++) {} // loop runs n times
for(var i=0; i<100000; i++) { // loop runs 100000*n times
  for (var i=0; j<n; j++) {}
}

O(log n): ตัวประกอบลอการิทึม(base2) ของ 'n'

หากอยู่ในลูป ค่าของ 'i' จะลดลง ครึ่งหนึ่ง(เพราะ base2) หรือเพิ่มขึ้น สองครั้ง ของค่าในการวนซ้ำแต่ละครั้ง

/*
* for n=256, loop runs 8 times
* for n=128, loop runs 7 times
* for n=016, loop runs 4 times
* looks like "log2 n" in picture
*/
for(var i=n; i>=0; i/=2) {}  // i reduces by 1/2 in each iteration
for(var i=0; i<n; i*=2) {}  // i increases by *2 in each iteration

หาก 'i' ลด หนึ่งในสาม ในการวนซ้ำแต่ละครั้ง ให้บันทึก (base3):

/*
* for n=003, loop runs 1 times
* for n=009, loop runs 2 times
* for n=027, loop runs 3times
* looks like "log3 n" in picture
*/
for(var i=n; i>=0; i/=3) {}
// or
for(var i=0; i<n; i*=3) {}

เช่นเดียวกับความซับซ้อน log7 n 'i' ควรลดลงหนึ่งในเจ็ดในแต่ละการวนซ้ำ

for(var i=0; i<n; i*=7) {}
for(var i=n; i>=0; i/=7) {}

ตอนนี้เราสามารถมิกซ์แอนด์แมทช์กับความซับซ้อนพื้นฐานของเราได้แล้ว

for(var i=0; i<n; i*=7) { // O(log7 n)
  for(var j=0; j<n; j++) {} // O(n)
}
// Total complexity: O(n * log7 n)

สิ่งที่ควรทราบ: ความซับซ้อนของสิ่งหนึ่งภายในอีกสิ่งหนึ่งจะทวีคูณโดยที่เมื่อรวมกันแล้ว: เพิ่ม

มันสนุกใช่มั้ยล่ะ มาดูวิธีที่น่าสนใจเพิ่มเติมในการระบุความซับซ้อนในส่วนถัดไป!

O(บันทึก บันทึก n):

'i' เพิ่มขึ้น กำลังสอง หรือลดลงโดย รากที่สอง:

// Complex examples:
for (var i=0; i<n; i++) {
  for (var j=2; j<=n; j++){   
    j=j*j;
  }
}
/*
* n=2;      2^1   2^(2^0)  i: 0...1     j:2(1 time)
* n=4;      2^2   2^(2^1)  i: 0...3     j:2,4 (2 times)
* n=16;     2^4   2^(2^2)  i: 0...15    j:2,4,16 (3 times)
* n=256;    2^8   2^(2^3)  i: 0...155   j:2,4,16,256 (4 times)
* n=65536;  2^16  2^(2^4)  i: 0...65535 j:2,4,16,256,65536 (5 times)
* 
* we can see that i's loop runs n times
* whereas j's loop runs k+1 times where
* 2^(2^k) = n
* log(2^(2^k)) = log n
* 2^k = log n
* log(2^k) = log log n
* k = log log n
* 
* So total complexity of above program is: O(n (log (log n))) 🤯
*
* */

ตอนนี้เราต้องใช้เวลาและความพยายามเพียงเล็กน้อย ในตัวอย่างฐานของบันทึกที่กำหนดคือ 2 สำหรับฐานอื่นคุณรู้ว่าต้องทำอะไร สิ่งเดียวกับที่เราทำกับความซับซ้อนของ log n ในตัวอย่างก่อนหน้านี้
สนุกยิ่งขึ้นในตอนหน้า!

ไชโย 🍻