Bài tập về nhà của chữ O Big - Phân tích thuật toán phân đoạn mã?

Question

Đối với bài tập về nhà, tôi đã đưa ra 8 đoạn mã sau đây để phân tích và đưa ra một ký hiệu Big-Oh cho thời gian chạy. Ai có thể cho tôi biết nếu tôi đi đúng hướng không?

//Fragment 1 
for(int i = 0; i < n; i++) 
    sum++; 

Tôi đang nghĩ đến O (N) cho đoạn 1

//Fragment 2 
for(int i = 0; i < n; i+=2) 
    sum++; 

O (N) cho đoạn 2 cũng

//Fragment 3 
for(int i = 0; i < n; i++) 
    for(int j = 0; j < n; j++) 
     sum++; 

O (N^2) cho đoạn 3

//Fragment 4 
for(int i = 0; i < n; i+=2) 
    sum++; 
for(int j = 0; j < n; j++) 
    sum++; 

O (N) cho đoạn 4

//Fragment 5 
for(int i = 0; i < n; i++) 
    for(int j = 0; j < n * n; j++) 
     sum++; 

O (N^2) cho đoạn 5 nhưng n * n được ném tôi ra một chút vì vậy tôi không hoàn toàn chắc chắn

//Fragment 6 
for(int i = 0; i < n; i++) 
    for(int j = 0; j < i; j++) 
     sum++; 

O (N^2) cho đoạn 6 như cũng

//Fragment 7 
for(int i = 0; i < n; i++) 
    for(int j = 0; j < n * n; j++) 
     for(int k = 0; k < j; k++) 
      sum++; 

O (N^3) cho đoạn 7 nhưng một lần nữa n * n được ném tôi ra khỏi

//Fragment 8 
for(int i = 1; i < n; i = i * 2) 
    sum++; 

O (N) cho đoạn 8

Answer 1

Tôi nghĩ đoạn 5 là O (n^3) và đoạn tương tự 7 là O (n^5) *. Nó cũng giống như O (log (n)) cho mảnh 8.

Đối với các vấn đề n * n, bạn phải thực thi thân của vòng lặp n * n lần, vì vậy nó sẽ là O (n^2) , sau đó bạn hợp chất với thứ tự của mã khác. Đoạn 8 thực sự tăng gấp đôi số lượt truy cập thay vì tăng nó, do đó vấn đề lớn hơn, công việc ít hơn bạn phải làm, vì vậy nó là O (log (n))

* chỉnh sửa: Fragment 7 is O (n^5), không phải O (n^4) như tôi đã từng nghĩ. Điều này là do cả hai j và k chuyển từ 1 thành n * n. Xin lỗi tôi đã không bắt được điều này trước đó.

Answer 2

Dường như bạn đang đi đúng hướng. Liên quan đến N * N bạn nghĩ nó có hiệu quả gì? Nó là một yếu tố khác của N nên nó có thể sẽ là thứ tự cao hơn.

Chỉ là một cảnh báo, tôi thấy một bài đăng khác như thế này và nó đã bị vô hiệu. Hãy cẩn thận. Here là bài đăng.

Answer 3

Đối với trường hợp 8 thử viết ra số lần lặp lại cho một số giá trị của N và xem những gì mô hình trông giống như ... nó không phải là O (N)

Answer 4

Fragment 7 là O (n^5) , không phải O (n^4) như các lời nhận xét nhận xét hiện đang được chấp nhận. Nếu không, nó là chính xác.

Answer 5

Bạn đang đi đúng hướng, nhưng đây là mẹo về cách mọi thứ có thể rõ ràng hơn trên đường đi. Giả sử bạn có một số mã:

for(i = 0; i < n; i++) { 
    for(j = 0; j < 100; j++){....} 
} 

Đúng, hãy xem xét thực tế là bạn có mã ở các cấp khác nhau.Trong ví dụ này, bạn chỉ có thể xem 3 cấp cho đến nay:

1. Các bên ngoài cho vòng lặp mà đi từ 0-n
2. Một cho vòng lặp mà đi từ 0-100
3. Một số mã bên trong, được đánh dấu là ...

Không có lúc nào bạn nên tính toán tất cả trong 1 lần. Đây là nơi mà hầu hết người mới bắt đầu thực hiện một số loại lỗi số học. Tính nó riêng cho từng cấp độ và sau đó nhân tất cả lại với nhau.

Chúc may mắn!