Ký hiệu Big O cho số tam giác?

Question

Ký hiệu O lớn chính xác cho thuật toán chạy trong thời gian triangular là gì? Dưới đây là ví dụ:

func(x): 
    for i in 0..x 
    for j in 0..i 
     do_something(i, j) 

Bản năng đầu tiên của tôi là O(n²), nhưng tôi không hoàn toàn chắc chắn.

Answer 1

Có, N * (N + 1)/2, khi bạn thả các hằng số và các thuật ngữ bậc thấp hơn, khiến bạn có N-bình phương.

Answer 2

Vâng, O(n^2) chắc chắn là chính xác. Nếu tôi nhớ chính xác, O luôn là giới hạn trên, vì vậy, O(n^3) cũng phải là IMO, cũng như O(n^n) hoặc bất kỳ thứ gì. Tuy nhiên O(n^2) dường như là một trong những chặt chẽ nhất có thể dễ dàng khấu trừ.

Answer 3

Nếu bạn nghĩ về mặt toán học, diện tích của tam giác bạn đang tính là ((n+1)^2)/2. Do đó, thời gian tính toán: O ((((+ 1)^2)/2)

Answer 4

Thời gian tính toán tăng theo hệ số N * (N + 1)/2 cho mã này. Đây là bản chất O (N^2).

Answer 5

khi tăng đầu vào từ N đến 2n sau đó thời gian chạy của thuật toán của bạn sẽ tăng từ t đến 4t

do đó thời gian chạy là tỷ lệ thuận với bình phương của kích thước đầu vào

nên thuật toán là O (n^2)

Answer 6

O (! n) xử lý các trường hợp để tính toán giai thừa (thời gian tam giác).

Nó cũng có thể được biểu diễn dưới dạng O (n^2) đối với tôi điều này có vẻ hơi sai lệch vì số tiền được thực hiện luôn bằng một nửa so với O (n^2) sẽ thực hiện.