สัญกรณ์ขนาดใหญ่ในโครงสร้างข้อมูล: ทุกสิ่งที่ต้องรู้

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

สัญกรณ์ Big O หมายถึงสัญกรณ์ทางคณิตศาสตร์ที่ทำหน้าที่เป็นปัจจัยจำกัดของฟังก์ชันใดๆ เมื่ออาร์กิวเมนต์มีแนวโน้มที่จะเอนเอียงไปทางค่าเฉพาะหรืออนันต์ มันอยู่ในหมวดหมู่ของสัญกรณ์คณิตศาสตร์ที่ Edmund Landau, Paul Bachmann และอื่น ๆ คิดค้น ดังนั้นจึงเรียกรวมกันว่าสัญกรณ์ Bachmann–Landau หรือสัญกรณ์ asymptotic

ตามการหักทางคณิตศาสตร์ ฟังก์ชันสองฟังก์ชัน f(n) และ g(n) ถูกกำหนดบนชุดของจำนวนบวกหรือจำนวนจริงที่ไม่ผูกมัด ในที่นี้ g(n) เป็นค่าบวกอย่างเคร่งครัดสำหรับทุกค่าขนาดใหญ่ของ n สามารถเขียนได้ดังนี้

f(n) = O(g(n)) โดยที่ n มีแนวโน้มเป็นอนันต์ (n → ∞)

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

ฉ(n) = O(ก.(n))

ในที่นี้ f และ g เป็นฟังก์ชันที่จำเป็นซึ่งเริ่มต้นจากจำนวนเต็มบวกไปจนถึงจำนวนจริงที่ไม่ใช่ค่าลบ

ดังนั้น ค่า n จำนวนมากจึงแสดงโดย Big O asymptotic

คุณสมบัติของ สัญลักษณ์ Big O ในโครงสร้างข้อมูล

อัลกอริทึม Big O ในโครงสร้างข้อมูล มีคุณสมบัติที่จำเป็นค่อนข้างน้อย คุณสมบัติที่สำคัญดังกล่าวของ Big O Notation มีดังนี้:

• ฟังก์ชันการรวม:
  ถ้า f(n) = f 1 (n) + f 2 (n) + — + f m (n) และ f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  แล้ว O(f(n)) = O(สูงสุด(f1(n), f2(n), –, fm(n)))
• ฟังก์ชันลอการิทึม:
  ถ้า f(n) = โลแกน และ g(n)=logbn
  แล้ว O(f(n))=O(g(n))
• การคูณคงที่:
  ถ้า f(n) = cg(n) ดังนั้น O(f(n)) = O(g(n)) โดยที่ c เป็นค่าคงที่ที่ไม่ใช่ศูนย์
• ฟังก์ชันพหุนาม:
  ถ้า f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  แล้ว O(f(n)) = O(นาโนเมตร)

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

สำรวจหลักสูตรวิศวกรรมซอฟต์แวร์ยอดนิยมของเรา

ที่นี่ ในขณะที่พูดถึง Big O ทุกฟังก์ชันบันทึกเดียวก็เพิ่มขึ้นเช่นเดียวกัน

ความสำคัญของสัญกรณ์ Big O ในการวิเคราะห์รันไทม์ของอัลกอริทึม

ความซับซ้อนของเวลาทำงานที่แย่ที่สุดของอัลกอริธึมถูกใช้เพื่อเปรียบเทียบและคำนวณ โดยเฉพาะอย่างยิ่งในกรณีของการวิเคราะห์ประสิทธิภาพของอัลกอริธึม ลำดับของ O(1) ซึ่งแสดงเป็น Constant Running Time เป็นเวลาทำงานที่เร็วที่สุดของอัลกอริทึม – เวลาที่อัลกอริทึมใช้จะเท่ากันสำหรับขนาดอินพุตต่างๆ สิ่งสำคัญคือต้องสังเกตว่ารันไทม์ในอุดมคติของอัลกอริธึมคือเวลารันคงที่ ซึ่งทำได้ไม่บ่อยนัก เนื่องจากรันไทม์ของอัลกอริธึมขึ้นอยู่กับขนาดอินพุตของ n

ตัวอย่างเช่น:

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

• n = 20
  บันทึก (20) = 2.996;
  20 = 20;
  20 บันทึก (20) = 59.9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2.432902 + 18 18 ;
• n = 10
  บันทึก (10) = 1;
  10 = 10;
  10 บันทึก (10) = 10;
  10 2 = 100;
  2 10 = 1024;
  10! = 3628800;

ประสิทธิภาพรันไทม์ของอัลกอริธึมคำนวณในทำนองเดียวกัน

ต่อไปนี้คือตัวอย่างอัลกอริทึมอื่นๆ ของการวิเคราะห์รันไทม์ –

• เมื่อพูดถึง Linear Search ความซับซ้อนของรันไทม์คือ O(n)
• ความซับซ้อนของรันไทม์คือ O(log n) สำหรับการค้นหาแบบไบนารี
• สำหรับ Selection Sort, Bubble Sort, Bucket Sort, Insertion Sort ความซับซ้อนของรันไทม์คือ O(n^c)
• เมื่อพูดถึงอัลกอริธึมเอ็กซ์โปเนนเชียล เช่น หอคอยฮานอย ความซับซ้อนของรันไทม์คือ O(c^n)
• สำหรับ Merge SortSort และ Heap Sort ความซับซ้อนของรันไทม์คือ O(n log n)

Big O วิเคราะห์ความซับซ้อนของอวกาศอย่างไร?

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

สำหรับการกำหนดความซับซ้อนของพื้นที่ของอัลกอริทึม เราต้องปฏิบัติตามสองภารกิจนี้ –

ภารกิจที่ 1: การนำโปรแกรมไปใช้สำหรับอัลกอริธึมเฉพาะเป็นสิ่งสำคัญ

ภารกิจที่ 2: จำเป็นต้องทราบขนาดของอินพุต n เพื่อกำหนดหน่วยความจำที่แต่ละรายการจะเก็บไว้

งานสำคัญทั้งสองนี้จำเป็นต้องทำให้สำเร็จก่อนที่จะคำนวณความซับซ้อนของพื้นที่สำหรับอัลกอริทึม

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

มีตัวอย่างมากมายของอัลกอริธึมที่มีความซับซ้อนของพื้นที่ ซึ่งบางส่วนได้รับการกล่าวถึงด้านล่างเพื่อความเข้าใจที่ดีขึ้นของอัลกอริทึมประเภทนี้:

• สำหรับการเรียงลำดับแบบบับเบิ้ล, การค้นหาเชิงเส้น, การเรียงลำดับการเลือก, การเรียงลำดับการแทรก, การเรียงลำดับฮีป และการค้นหาไบนารี ความซับซ้อนของช่องว่างคือ O(1 )
• ความซับซ้อนของพื้นที่คือ O(n+k) เมื่อพูดถึง radix sort
• ความซับซ้อนของพื้นที่คือ O(n) สำหรับ SortSort อย่างรวดเร็ว
• ความซับซ้อนของพื้นที่คือ O(log n) สำหรับการเรียงลำดับการผสาน

ตัวอย่างสัญลักษณ์ Big O ใน C

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

ด้านล่างนี้ คุณจะพบอัลกอริธึมการเรียงลำดับการเลือกในภาษา C ซึ่งมีการคำนวณความซับซ้อนของตัวพิมพ์ใหญ่ที่สุด (สัญลักษณ์ Big O) ของอัลกอริทึม:-

สำหรับ(int i=0; i<n; i++)

{

int นาที = ผม;

สำหรับ(int j=i; j<n; j++)

{

if(array[j]<array[นาที])

มิน=เจ;

}

int temp = อาร์เรย์[i];

อาร์เรย์[i] = อาร์เรย์[นาที];

อาร์เรย์[นาที] = อุณหภูมิ;

}

ในการวิเคราะห์อัลกอริทึม:

• สามารถระบุได้แล้วว่าช่วงของ for outer loop คือ i < n ซึ่งระบุว่าลำดับของลูปคือ O(n)
• ต่อไป เราสามารถระบุได้ว่ามันเป็น O(n) ด้วย j < n สำหรับ inner for loop
• ค่าคงที่จะถูกละเว้น แม้ว่าจะพบประสิทธิภาพเฉลี่ย n/2 สำหรับค่าคงที่ c ดังนั้น ลำดับคือ O(n)
• หลังจากการคูณลำดับของวงในและวงนอก ความซับซ้อนของรันไทม์ที่ได้คือ O(n^2)

อัลกอริธึมอื่นๆ ใน C สามารถใช้งานได้ง่าย โดยสามารถวิเคราะห์และกำหนดความซับซ้อนได้ง่ายเช่นเดียวกัน

การใช้สัญกรณ์บิ๊กโอ

มีสองส่วนหลักที่ใช้ Big O Notation:-

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

อย่างไรก็ตาม ในทั้งสองแอปพลิเคชัน ฟังก์ชัน g ( x ) ที่ปรากฏภายใน O (·) มักถูกเลือกให้ใช้งานได้ง่ายที่สุด หากไม่ระบุเงื่อนไขลำดับที่ต่ำกว่าและปัจจัยคงที่

มีการใช้สัญกรณ์นี้อีกสองแบบที่ใกล้เคียงกันอย่างเป็นทางการแต่ค่อนข้างแตกต่างกัน พวกเขาคือ:-

• อนันต์ asymptotics
• การแสดงอาการไม่สิ้นสุด

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

อ่านบทความยอดนิยมของเราเกี่ยวกับการพัฒนาซอฟต์แวร์

บทสรุป

โดยสรุป เราสามารถพูดได้ว่า Big Data มีบทบาทสำคัญในโครงสร้างข้อมูล และการมีความรู้เชิงลึกเกี่ยวกับ Big O notation เป็นทักษะที่ยอดเยี่ยม มีความต้องการสูงในภาคงานและอาจเป็นทางเลือกที่ดีสำหรับเส้นทางอาชีพ โปรแกรมใบรับรองขั้นสูง ของ upGrad ใน Big Data จะช่วยให้คุณมีเลเวอเรจที่คุณต้องการเพื่อส่งเสริมอาชีพของคุณ ซึ่งจะแนะนำทักษะระดับมืออาชีพชั้นนำ เช่น การประมวลผลข้อมูลด้วย PySpark, Data Warehousing, MapReduce, การประมวลผลข้อมูลขนาดใหญ่บน AWS Cloud, การประมวลผลแบบเรียลไทม์ เป็นต้น