สวัสดี! บทเรียนวันนี้จะแตกต่างจากที่เหลือเล็กน้อย จะต่างกันตรงที่เกี่ยวข้องกับ Java ทางอ้อมเท่านั้น ที่กล่าวว่าหัวข้อนี้มีความสำคัญมากสำหรับโปรแกรมเมอร์ทุกคน เราจะพูดถึงอัลกอริทึม อัลกอริทึมคืออะไร? พูดง่ายๆ ก็คือเป็นลำดับของการกระทำที่ต้องทำให้เสร็จเพื่อให้ได้ผลลัพธ์ที่ต้องการ เราใช้อัลกอริทึมบ่อยครั้งในชีวิตประจำวัน ตัวอย่างเช่น ทุกเช้าคุณมีงานเฉพาะ: ไปโรงเรียนหรือที่ทำงาน และในขณะเดียวกันก็:
- เสื้อผ้า
- ทำความสะอาด
- เลี้ยง
- ปลุกโดยใช้นาฬิกาปลุก
- อาบน้ำและล้างตัว
- ทำอาหารเช้าและกาแฟหรือชา
- กิน.
- หากคุณไม่ได้รีดผ้าในเย็นวันก่อน ให้รีด
- แต่งตัว.
- ออกจากบ้าน.
- ซื้อหรือดาวน์โหลดพจนานุกรม New International ฉบับที่สามของเว็บสเตอร์ฉบับปี 1961
- ค้นหาทุกชื่อจากรายการของเราในพจนานุกรมนี้
- เขียนหน้าพจนานุกรมที่ชื่อนั้นลงบนกระดาษ
- ใช้เศษกระดาษเพื่อจัดเรียงชื่อ
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)
GO TO FULL VERSION