Ví dụ về Big O của 2^n

Question

Vì vậy, tôi có thể hình dung thuật toán nào có độ phức tạp của n^c, chỉ là số lượng lồng nhau cho vòng lặp.

for (var i = 0; i < dataset.len; i++ { 
    for (var j = 0; j < dataset.len; j++) { 
     //do stuff with i and j 
    } 
} 

Nhật ký là thứ chia tách bộ dữ liệu trong nửa thời gian, tìm kiếm nhị phân thực hiện điều này (không hoàn toàn chắc chắn mã này trông như thế nào).

Nhưng ví dụ đơn giản về thuật toán là c^n hoặc cụ thể hơn là 2^n. O (2^n) có dựa trên các vòng lặp thông qua dữ liệu không? Hoặc cách dữ liệu được tách ra? Hoặc cái gì khác hoàn toàn?

Answer 1

Thuật toán với thời gian chạy O (2^N) thường là thuật toán đệ quy giải quyết vấn đề về kích thước N bằng cách đệ quy giải hai vấn đề nhỏ hơn về kích thước N-1.

Chương trình này, ví dụ in ra tất cả các bước cần thiết để giải quyết "Towers Hà Nội" nổi tiếng vấn đề đối với N đĩa trong pseudo-code

void solve_hanoi(int N, string from_peg, string to_peg, string spare_peg) 
{ 
    if (N<1) { 
     return; 
    } 
    if (N>1) { 
     solve_hanoi(N-1, from_peg, spare_peg, to_peg); 
    } 
    print "move from " + from_peg + " to " + to_peg; 
    if (N>1) { 
     solve_hanoi(N-1, spare_peg, to_peg, from_peg); 
    } 
} 

Hãy T (N) là thời gian cần thiết cho N đĩa.

Chúng tôi có:

T(1) = O(1) 
and 
T(N) = O(1) + 2*T(N-1) when N>1 

Nếu bạn liên tục mở rộng hạn cuối cùng, bạn nhận được:

T(N) = 3*O(1) + 4*T(N-2) 
T(N) = 7*O(1) + 8*T(N-3) 
... 
T(N) = (2^(N-1)-1)*O(1) + (2^(N-1))*T(1) 
T(N) = (2^N - 1)*O(1) 
T(N) = O(2^N) 

Để thực sự con số này ra, bạn chỉ cần phải biết rằng mẫu nhất định trong mối quan hệ tái phát dẫn đến kết quả theo cấp số mũ. Nói chung, T(N) = ... + C*T(N-1) với C > 1 có nghĩa là O (x^N). Xem:

https://en.wikipedia.org/wiki/Recurrence_relation

Answer 2

Suy nghĩ về ví dụ lặp qua tất cả các tập hợp con có thể có của một tập hợp. Loại thuật toán này được sử dụng cho một vấn đề ba lô tổng quát.

Nếu bạn cảm thấy khó hiểu cách lặp qua các tập con dịch sang O (2^n), hãy tưởng tượng một bộ công tắc n, mỗi bộ tương ứng với một phần tử của tập hợp. Bây giờ, mỗi thiết bị chuyển mạch có thể được bật hoặc tắt. Hãy suy nghĩ về "trên" như là trong tập hợp con. Lưu ý, có thể kết hợp bao nhiêu: 2^n.

Nếu bạn muốn xem một ví dụ trong mã, thường dễ nghĩ về đệ quy ở đây, nhưng tôi không thể nghĩ ra bất kỳ ví dụ tốt đẹp và kém ổn định nào khác ngay bây giờ.

Answer 3

int Fibonacci(int number) 
{ 
    if (number <= 1) return number; 

    return Fibonacci(number - 2) + Fibonacci(number - 1); 
} 

Tăng trưởng tăng gấp đôi với mỗi phụ kiện cho bộ dữ liệu đầu vào. Đường cong tăng trưởng của hàm O (2N) là hàm mũ - bắt đầu từ rất nông, sau đó tăng lên một cách thiên nhiên. dụ của tôi về O lớn (2^n), nhưng tốt hơn nhiều là thế này:

public void solve(int n, String start, String auxiliary, String end) { 
    if (n == 1) { 
     System.out.println(start + " -> " + end); 
    } else { 
     solve(n - 1, start, end, auxiliary); 
     System.out.println(start + " -> " + end); 
     solve(n - 1, auxiliary, start, end); 
    } 

Trong chương trình phương pháp này in tất cả các động thái để giải quyết "Tháp Hà Nội" vấn đề. Cả hai ví dụ đều sử dụng đệ quy để giải quyết vấn đề và có thời gian chạy O (2^n) lớn.

Answer 4

c^N = Tất cả sự kết hợp của các yếu tố từ n một bảng chữ cái có kích thước c.

Cụ thể hơn 2^N là tất cả các số có thể biểu diễn bằng N bit.

Các trường hợp thông thường được thực hiện một cách đệ quy, một cái gì đó như:

vector<int> bits; 
int N 
void find_solution(int pos) { 
    if (pos == N) { 
    check_solution(); 
    return; 
    } 
    bits[pos] = 0; 
    find_solution(pos + 1); 
    bits[pos] = 1; 
    find_solution(pos + 1); 
}