อธิบาย Big Theta และ Asymptotic Notation

Big Omega บอกขอบเขตล่างของรันไทม์ของฟังก์ชันและ Big O จะบอกขอบเขตบน

บ่อยครั้งที่มันแตกต่างกันและเราไม่สามารถรับประกันรันไทม์ได้ - มันจะแตกต่างกันไประหว่างสองขอบเขตและอินพุต แต่จะเกิดอะไรขึ้นเมื่อมันเหมือนกัน? จากนั้นเราสามารถให้theta (Θ) ที่ถูกผูกไว้ - ฟังก์ชันของเราจะทำงานในช่วงเวลานั้นไม่ว่าเราจะป้อนข้อมูลใดก็ตาม

โดยทั่วไปเราต้องการให้ theta ถูกผูกไว้เสมอถ้าเป็นไปได้เพราะเป็นขอบเขตที่แม่นยำและแน่นที่สุด ถ้าเราไม่สามารถให้ theta ถูกผูกไว้ได้สิ่งที่ดีที่สุดถัดไปคือ O ที่ถูกผูกไว้ให้แน่นที่สุด

ยกตัวอย่างเช่นฟังก์ชันที่ค้นหาอาร์เรย์สำหรับค่า 0:

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false
  1. กรณีที่ดีที่สุดคืออะไร? ถ้าอาร์เรย์ที่เราให้มี 0 เป็นค่าแรกจะใช้เวลาคงที่: Ω (1)
  2. กรณีที่เลวร้ายที่สุดคืออะไร? ถ้าอาร์เรย์ไม่มี 0 เราจะวนซ้ำผ่านอาร์เรย์ทั้งหมด: O (n)

เราให้โอเมก้ากับโอผูกพันแล้วทีต้าล่ะ? เราให้มันไม่ได้! ขึ้นอยู่กับอาร์เรย์ที่เราให้ไว้รันไทม์จะอยู่ระหว่างค่าคงที่และเชิงเส้น

มาเปลี่ยนรหัสกันหน่อย

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

คุณนึกถึงกรณีที่ดีที่สุดและกรณีที่เลวร้ายที่สุด ?? ฉันทำไม่ได้! ไม่ว่าเราจะให้อาร์เรย์ใดก็ตามเราต้องวนซ้ำทุกค่าในอาร์เรย์ ดังนั้นฟังก์ชันจะใช้เวลาอย่างน้อย n (Ω (n)) แต่เราก็รู้ด้วยว่าจะใช้เวลาไม่เกิน n เวลา (O (n)) สิ่งนี้หมายความว่า? ฟังก์ชั่นของเราจะใช้เวลาตรง n เวลา: Θ (n)

หากขอบเขตสับสนให้คิดเช่นนี้ เรามีเลข 2 ตัวคือ x และ y เราได้รับว่า x <= y และ y <= x ถ้า x น้อยกว่าหรือเท่ากับ y และ y น้อยกว่าหรือเท่ากับ x ดังนั้น x ต้องเท่ากับ y!

หากคุณคุ้นเคยกับรายการที่เชื่อมโยงลองทดสอบตัวเองและคิดถึงเวลาทำงานของแต่ละฟังก์ชันเหล่านี้!

  1. ได้รับ
  2. ลบ
  3. เพิ่ม

สิ่งต่างๆจะน่าสนใจยิ่งขึ้นเมื่อคุณพิจารณารายการที่เชื่อมโยงเป็นทวีคูณ!

สัญกรณ์ Asymptotic

เราจะวัดค่าประสิทธิภาพของอัลกอริทึมได้อย่างไร?

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

เราทำได้โดยการกำหนดขีด จำกัด ทางคณิตศาสตร์ของอัลกอริทึม นี่คือ big-O, big-omega และ big-theta หรือสัญกรณ์ asymptotic ของอัลกอริทึม ในกราฟ big-O จะเป็นอัลกอริทึมที่ยาวที่สุดที่สามารถใช้กับชุดข้อมูลใดก็ได้หรือ "ขอบเขตบน" โอเมก้าตัวใหญ่เปรียบเสมือนสิ่งที่ตรงกันข้ามกับบิ๊กโอคือ“ ขอบเขตล่าง” นั่นคือจุดที่อัลกอริทึมมาถึงความเร็วสูงสุดสำหรับชุดข้อมูลใด ๆ Big theta เป็นค่าประสิทธิภาพที่แน่นอนของอัลกอริทึมหรือช่วงที่มีประโยชน์ระหว่างขอบเขตบนและล่างที่แคบ

ตัวอย่างบางส่วน:

  • “ การจัดส่งจะอยู่ที่นั่นภายในชีวิตของคุณ” (ใหญ่ -O ขอบบน)
  • “ ฉันจ่ายให้คุณได้อย่างน้อยหนึ่งดอลลาร์” (โอเมก้าตัวใหญ่ขอบล่าง)
  • “ จุดสูงสุดในวันนี้คือ25ºCและต่ำสุดจะเป็น19ºC” (บิ๊กทีต้าแคบ)
  • “ เดินไปชายหาดประมาณ 1 กิโลเมตร” (big-theta แน่นอน)

ข้อมูลมากกว่านี้:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-notation-represent //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/