Vì vậy, chúng ta hãy thực hành ý tưởng so sánh hai đa thức,
ví dụ, và quyết định xem
chúng có thuộc cùng một lớp hay không.
Vì vậy, chúng tôi định nghĩa lớp chính nó.
Để làm điều đó, chúng ta bắt
đầu với ý tưởng ký hiệu Big-O,
mà đôi khi được biểu thị là
gạch chân o trong văn bản viết tay.
Thủ tục ở đây là như sau.
Về cơ bản, giả định rằng chúng ta có hai hàm của chúng ta
như x bình phương và 5x bình phương trừ 100x.
Chúng ta, bằng cách nào đó, đang nói
về ranh giới trên của
một chức năng liên quan đến chức năng khác.
Về cơ bản, nó có nghĩa là một hàm lớn
hơn không nhiều hơn trong một
số lần cố định hơn một số lần khác.
Nói cách khác, chúng ta cần phải viết ra một bất đẳng thức ở đây.
Về cơ bản, giả sử rằng chúng ta có một số khu phố
của một điểm nhất định, một, ví dụ.
Chúng tôi gọi một chức năng
Big-O từ một chức năng khác trong khu phố này.
Nếu có một số hằng số, hằng số
dương, C như quan hệ,
giá trị tuyệt đối của các quan hệ của các
hàm f và g không vượt quá
giá trị này c Vì vậy, chúng ta hãy xem xét,
ví dụ, trường hợp của chúng ta.
Chúng ta có x bình phương,
ví dụ, chúng ta hãy gọi nó là f là x bình phương,
g là 5x bình phương trừ
100x và tôi sẽ giả định rằng x tiếp cận vô cùng.
Vì vậy, những gì chúng ta sẽ làm, chúng ta sẽ nói,
là một số chức năng lớn hơn chức năng
khác trong một số khu vực vô cùng.
Chúng ta cần phải viết
ra một cái gì đó giống như giá trị tuyệt đối của f
là ít hơn hoặc bằng một số
hằng số nhân với giá trị tuyệt đối của g, được chứ?
Nói cách khác, x bình phương nhỏ hơn hoặc lớn hơn một số
hằng số nhân với Epsilon
[không nghe được] 5x bình phương trừ 100x.
Nó khá dễ dàng để hiểu những gì
hằng số là thực sự tốt cho chúng ta ở đây.
Ví dụ, chúng ta hãy bắt
đầu với hằng số c, bằng một.
Vâng, rõ ràng là nó là,
bởi vì nếu chúng ta chỉ giả định rằng c bằng một.
Như vậy, chúng ta nhận được x bình phương ở một bên và
5x ô vuông trừ 100x ở phía bên kia.
Nếu chúng ta trừ x bình phương
từ cả hai bên, do đó, chúng ta nhận được các hàm,
mà rõ ràng là dương tính từ một số điểm,
bởi vì chúng ta đang nhìn vào
một hàm parabol với dương tính.
Hệ số của tôi, do đó,
có một gốc và sau gốc này,
chúng tôi chỉ có giá trị tích cực.
Như vậy, sự bất đẳng thức này giữ và một.
F là Big-O về phía G,
đó là một ví dụ.
Một mã dễ dàng lập luận rằng nếu chúng ta
cần trao đổi chức năng này mà vẫn giữ,
chỉ vì thay vì viết c bằng một.
Hãy để chúng tôi cố gắng làm điều này giải thích ở đây.
Vì vậy, về cơ bản, chúng ta cần phải chứng minh một điều gì đó, như thế này ở đây.
Vì vậy, để làm mỗi,
chúng ta cần phải xem xét một c vô ích,
nhỏ, nhưng một cái tuyệt vời.
Vì vậy, về cơ bản, chúng tôi bắt đầu với như c bằng năm.
Sau đó, chúng tôi nhận được một kết quả tốt đẹp ở đây.
Nhưng nó không phải lúc nào cũng như vậy, bởi vì, ví dụ,
chúng ta hãy nhìn vào một số trường hợp thú vị hơn.
Ví dụ, những gì các hàm [không nghe được],
sin của x và x,
như x tiếp cận bằng không? Chúng ta biết cái gì chứ?
Họ về cơ bản là tương đương như người ta mong đợi,
rằng sin x về cơ bản là một lớn O của x.
nó khá dễ dàng, bởi vì
giá trị tuyệt đối của sin x, như chúng ta đã nói, trong khi chúng ta
đang nói về giới hạn quan trọng thứ hai của chúng tôi,
bây giờ lớn hơn mô hình x,
bởi vì giá trị tuyệt đối của x
thực ra là diện tích của ngành,
và sin của x là diện tích của tam giác tương ứng.
Vì vậy, với điều đó, chúng tôi đếm rằng
bằng cách sử dụng một hằng số c bằng một,
chúng tôi nhận được điều này hoàn toàn đúng.
Nhưng nếu chúng ta thay thế một điểm quan tâm từ 0,
để chúng ta nói vô cùng?
Trước hết, những ý tưởng mà sin của x
là Big-o hướng tới x,
vẫn giữ ở thời điểm này, bởi vì về cơ bản,
sin của x không lớn hơn một và x là lớn nhất.
Như bạn có thể tưởng tượng, x tiếp cận vô cùng.
Như vậy, bất đẳng thức này vẫn giữ,
ví dụ, cho cùng một hằng số bằng một.
Nhưng nếu chúng ta thay đổi nó,
nếu chúng ta thay đổi hai hàm,
thì chúng ta nhận được 380,
[không nghe được] ở đây, bởi vì sin x
và x không liên quan trong thời gian.
Bởi vì sin x vẫn còn, xin lỗi,
Tôi đã nói với bạn rằng chúng ta cần
phải trao đổi chức năng và không làm điều đó.
Vì vậy, đó là một sự lừa dối tuyệt vời ở đây.
Điều đó ít dối trá hơn.
Vì vậy, x là Big-O từ sin của x
Vì vậy, về cơ bản, sin của x
được giới hạn bởi một và trừ một và x là không giới hạn.
Vì vậy, nếu chúng ta cố gắng đưa ra ý tưởng
rằng x nên nhỏ hơn một số hằng số,
nhân với sin của x và chúng ta nói rằng
hằng số này, ví dụ, 10.000.
Vậy lỗi là gì?
Sau đó, chúng ta có thể ví dụ,
lấy x lớn hơn hai, kể từ n,
phương trình này, chúng tôi sẽ gần như
chắc chắn chỉ rơi ra và
điều này là cực kỳ không phải là trường hợp.
Nó không đúng. Vì vậy, khi
chúng ta đang nói về ký hiệu Big-O,
bạn luôn cần phải xem xét thứ tự ở đây.
Chức năng gì, liên quan đến những gì chức năng? Nó có lớn không?