Đơn giản hóa độ phức tạp Big-O của thuật toán số mũ này

Question

Tôi có một thuật toán đếm mà tôi đang cố gắng để có được một mô tả lớn-o chung. Nó là khủng khiếp lồng nhau và khủng khiếp theo cấp số nhân. Ở đây là:

1. For each T_i in T 
2. For k = 1 to max_k 
3. For each of 2^k*(n choose k) items 
4. For each t in T_i 
5. check if the item is in t...etc. 

Dưới đây là một ý tưởng line-by-line của mỗi lần chạy

1. Đây là một phân vùng đơn giản và tôi sẽ chỉ cho nó một c1 liên tục.
2. max_k là một số nhỏ, luôn nhỏ hơn n, có lẽ khoảng 4 hoặc 5. Tôi sẽ sử dụng k bên dưới.
3. Vòng lặp này luôn chạy 2^k * (n chọn k) lần
4. Bằng cách xem xét dòng 1, chúng ta có thể khái quát hóa dòng này và biết nó sẽ không bao giờ cháy nhiều hơn 2^n lần trong trường hợp xấu nhất, nhưng nói chung sẽ chạy một phần của 2^n lần, vì vậy chúng tôi sẽ gọi một (2^n)/c2
5. Đây là thao tác if-statement đơn giản bên trong tất cả các vòng lặp, vì vậy c3.

Nhân tất cả này lại với nhau cho:

c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3 

Vì tôi muốn có một lớn-O đại diện, bỏ qua các hằng số cho:

k * 2^k * (n choose k) * (2^n) 

Được biết (n chọn k) giáp ở trên bởi (n * e/k)^k, như vậy:

O(k * 2^k * (n * e/k)^k * (2^n)) 

Nhiệm vụ của tôi trên là, những gì tôi có thể bỏ qua ở đây ... 2^n chắc chắn là thuật ngữ thống trị vì n luôn luôn lớn hơn k, và thường nhiều hơn như vậy. Điều này có thể được đơn giản hóa thành O (2^n) không? Hoặc O (2^khủng khiếp)? Hoặc tôi nên để trong 2^k, như trong O (2^k * 2^n)? (hoặc để lại tất cả các điều khoản trong?)

Sự hiểu biết của tôi là nếu k hoặc max_k có thể cạnh tranh hoặc vượt qua n, thì chúng rất quan trọng. Nhưng vì chúng luôn bị chi phối, chúng có thể bị loại bỏ như các điều kiện bậc thấp hơn của thời gian chạy đa thức? Tôi cho rằng tất cả các mớ hỗn độn thời gian chạy theo cấp số nhân đều gây nhầm lẫn cho tôi. Bất cứ lời khuyên nào cũng đươc đánh giá cao.

Answer 1

hiểu biết của tôi là nếu k hay max_k thể cạnh tranh hoặc vượt qua n, sau đó họ là rất quan trọng

Đúng, nhưng ngược lại không được - có nghĩa là - nó không thể bỏ qua khi nó nói đến ký hiệu O lớn, ngay cả khi nó không cạnh tranh với n. Chỉ có thể bỏ qua nếu max_k bị giới hạn với hằng số (có một hằng số c sao cho k <= c). Ví dụ: O(n * logk) thuật toán, không phải là O(n), vì hệ số k không bị ràng buộc và do đó tồn tại một k sao cho nlogk > c*n cho mỗi hằng số c.

Vì biểu thức bạn nhận là sản phẩm, tất cả những gì bạn có thể bỏ qua là hằng số, trong trường hợp của bạn - chỉ là e giúp bạn O(k*2^k * (n/k)^k * 2^n).

Nếu k là bị chặn, thì bạn có thể xóa biểu tượng khỏi biểu thức cũng như ký hiệu O lớn và bạn sẽ nhận được O(n^k* 2^n).Lưu ý rằng ngay cả trong trường hợp này, mặc dù n^k << 2^n, nó vẫn không thể bỏ qua, bởi vì đối với mỗi hằng số c tồn tại một số n sao cho c*2^n < n^k *2^n, vì vậy thuật toán không phải là O(2^n).

Các yếu tố nhỏ hơn có thể bị bỏ qua khi nói đến bổ sung. Nếu k < n thì O(n + k) = O(n), bởi vì có một hằng số c,N sao cho tất cả n > N: c*n < n + k, nhưng điều này tất nhiên là không đúng khi giao dịch với sản phẩm.