Độ phức tạp của thuật toán

Question

Độ phức tạp được đưa ra cho vấn đề sau là O (n). Không phải là O (n^2)? Đó là bởi vì vòng lặp bên ngoài là O (n) và bên trong cũng là O (n), do đó n * n = O (n^2)?

Bảng câu trả lời của câu hỏi này cho biết câu trả lời là O (n). Làm thế nào là có thể?

public static void q1d(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n; j++) { 
      count++; 
     } 
    } 
} 

Sự phức tạp của vấn đề sau là O (n^2), bạn có thể đạt được điều đó như thế nào? Ai đó có thể vui lòng xây dựng?

public static void q1E(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n/2; j++) { 
      count++; 
     } 
    } 
} 

Cảm ơn

Answer 1

Sự phức tạp của cả hai mã là O (n * n)

FIRST

Các vòng ngoài chạy n lần và vòng lặp bên trong dao động từ 0 to n-1 lần

so

total = 1 + 2 + 3 + 4 ... + n

mà nếu bạn thêm arithmetic progression là n * (n + 1)/2 là O(n*n)

THỨ HAI

Các vòng ngoài chạy n lần và vòng lặp bên trong dao động từ 0 to n-1/2 lần

nên

total = 1 + 1/2 + 3/2 + 4/2 ... + n/2

mà nếu bạn thêm các cấp số cộng là n * (n + 1)/4 cũng là O(n*n)

Answer 2

Ví dụ đầu tiên là O(n^2), vì vậy nó có vẻ như họ đã thực hiện một sai lầm. Để tính toán (không chính thức) ví dụ thứ hai, chúng ta có thể làm n * (n/2) = (n^2)/2 = O(n^2). Nếu điều này không có ý nghĩa, bạn cần phải đi và bàn chải ý nghĩa của một cái gì đó là O(n^k) là.

Answer 3

Trường hợp đầu tiên chắc chắn O(n^2)

là Thứ hai là O(n^2) cũng vì bạn bỏ qua hằng khi tính toán O lớn

Answer 4

phiếu trả lời của bạn là sai, các thuật toán đầu tiên rõ ràng O (n^2) là.

Ký hiệu Big-Oh là "trường hợp xấu nhất" vì vậy khi tính giá trị Big-Oh, chúng tôi thường bỏ qua phép nhân/chia theo hằng số.

Điều đó đang được nói, ví dụ thứ hai của bạn cũng là O (n^2) trong trường hợp xấu nhất bởi vì, mặc dù vòng lặp bên trong là "chỉ" 1/2 n, n là hệ số giới hạn rõ ràng. Trong thực tế thuật toán thứ hai sẽ ít hơn O (n^2) hoạt động - nhưng Big-Oh được dự định là một trường hợp "tồi tệ nhất" (tức là giới hạn tối đa), vì vậy số lượng hoạt động chính xác bị bỏ qua ủng hộ tập trung vào cách thuật toán hoạt động như n tiến tới vô cùng.

Answer 5

Cả hai đều là O(n^2). Câu trả lời của bạn sai. Hoặc bạn có thể đã viết câu hỏi không chính xác.