Giải thích ký hiệu Theta lớn và tiệm cận

Big Omega cho chúng ta biết giới hạn dưới của thời gian chạy của một hàm, và Big O cho chúng ta biết giới hạn trên.

Thông thường, chúng khác nhau và chúng tôi không thể đảm bảo về thời gian chạy - nó sẽ khác nhau giữa hai giới hạn và đầu vào. Nhưng điều gì sẽ xảy ra khi chúng giống nhau? Sau đó, chúng ta có thể đưa ra một giới hạn theta (Θ) - hàm của chúng ta sẽ chạy trong thời gian đó, bất kể chúng ta cung cấp đầu vào nào cho nó.

Nói chung, chúng tôi luôn muốn đưa ra một ràng buộc theta nếu có thể vì nó là ràng buộc chính xác nhất và chặt chẽ nhất. Nếu chúng ta không thể đưa ra ràng buộc theta, điều tốt nhất tiếp theo là ràng buộc O chặt chẽ nhất có thể.

Lấy ví dụ, một hàm tìm kiếm một mảng cho giá trị 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. Trường hợp tốt nhất là gì? Vâng, nếu mảng mà chúng tôi cung cấp cho nó có 0 là giá trị đầu tiên, thì nó sẽ mất thời gian không đổi: Ω (1)
  2. Trường hợp xấu nhất là gì? Nếu mảng không chứa 0, chúng ta sẽ lặp lại toàn bộ mảng: O (n)

Chúng tôi đã cho nó ràng buộc omega và O, vậy còn theta thì sao? Chúng tôi không thể cung cấp cho nó một! Tùy thuộc vào mảng mà chúng tôi cung cấp cho nó, thời gian chạy sẽ ở đâu đó giữa hằng số và tuyến tính.

Hãy thay đổi mã của chúng tôi một chút.

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

Bạn có thể nghĩ ra trường hợp tốt nhất và trường hợp xấu nhất không ?? Tôi không thể! Bất kể chúng ta cung cấp cho mảng nào, chúng ta phải lặp qua mọi giá trị trong mảng. Vì vậy, hàm sẽ mất ÍT NHẤT n thời gian (Ω (n)), nhưng chúng ta cũng biết rằng nó sẽ không lâu hơn n thời gian (O (n)). Điều đó có nghĩa là gì? Hàm của chúng ta sẽ mất đúng n thời gian: Θ (n).

Nếu các giới hạn là khó hiểu, hãy nghĩ về nó như thế này. Chúng ta có 2 số, x và y. Ta được cho rằng x <= y và y <= x. Nếu x nhỏ hơn hoặc bằng y và y nhỏ hơn hoặc bằng x thì x phải bằng y!

Nếu bạn đã quen với các danh sách được liên kết, hãy tự kiểm tra và nghĩ về thời gian chạy cho từng chức năng này!

  1. được
  2. tẩy
  3. thêm vào

Mọi thứ thậm chí còn thú vị hơn khi bạn xem xét một danh sách được liên kết kép!

Ký hiệu tiệm cận

Làm cách nào để chúng tôi đo lường giá trị hiệu suất của các thuật toán?

Hãy xem thời gian là một trong những nguồn tài nguyên quý giá nhất của chúng ta. Trong máy tính, chúng ta có thể đo lường hiệu suất bằng khoảng thời gian mà một quá trình cần để hoàn thành. Nếu dữ liệu được xử lý bởi hai thuật toán giống nhau, chúng tôi có thể quyết định cách triển khai tốt nhất để giải quyết một vấn đề.

Chúng tôi làm điều này bằng cách xác định các giới hạn toán học của một thuật toán. Đây là big-O, big-omega và big-theta, hoặc các ký hiệu tiệm cận của một thuật toán. Trên biểu đồ, big-O sẽ là khoảng thời gian dài nhất mà một thuật toán có thể thực hiện đối với bất kỳ tập dữ liệu nhất định nào, hay còn gọi là "giới hạn trên". Big-omega giống như đối lập với big-O, "giới hạn dưới". Đó là nơi thuật toán đạt tốc độ cao nhất cho bất kỳ tập dữ liệu nào. Theta lớn là giá trị hiệu suất chính xác của thuật toán hoặc phạm vi hữu ích giữa giới hạn trên và giới hạn dưới hẹp.

Vài ví dụ:

  • "Việc giao hàng sẽ ở đó trong suốt cuộc đời của bạn." (big-O, giới hạn trên)
  • "Tôi có thể trả cho bạn ít nhất một đô la." (big-omega, giới hạn dưới)
  • "Mức cao nhất hôm nay sẽ là 25ºC và mức thấp nhất sẽ là 19ºC." (lớn-theta, hẹp)
  • "Cách bãi biển một km đi bộ." (big-theta, chính xác)

Thêm thông tin:

//www.khanacademy.org/computing/computer-science/algorithm/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8-ký hiệu-đại diện //www.geeksforgeeks.org/analysis-of-algorithm-set-3asymptotic-notations/