Nhờ góp ý bài viết về Độ phức tạp thuật toán

Một ông khác lại bảo. Còn có cách khác nhanh hơn

bool is_prime(int n) {
    if (n < 2) return false;

    if ((n > 2) && (n % 2 == 0)) return false;

    const int max_divisor = floor(sqrt(n));

    for (int k = 3; k <= max_divisor; k += 2) 
        if (n % k == 0) return false;
    return true;
}

Không rõ cú pháp C cho lắm

Cũng được đấy =)) Nhưng mà viết code này không biết có em newbie nào nuốt nổi không :v

^ phần này là CS105 chứ ko phải 101

CS105 là sao ạ?
20 char…

computer science 105

105 vs 101 có ý nghĩa gì ạ?

CS có nhiều khóa học, giông ở Việt Nam học nhập môn lâp trinh-lâp trinh căn bản-cấu trúc dữ liệu… vậy đó:
Tùy theo mỗi trường mà nó có thể khác khác xí, thường thì hao hao nhau, ví dụ:
http://ucsd.edu/catalog/courses/CSE.html

UPD: Đã sửa theo góp ý của @graktung
Anh @nguyenhuuca có nhận gì về bài viết không ạ? Cho em học hỏi từ anh với ạ!

Nếu được thì em phân lớp độ phực tạp thuật toán ra: hang số, logN, N ,N^2, 2^N…
Mà viết vậy là khá đó chứ :D.

Em cảm ơn anh ạ

+1 và merge req rồi nhé :))

Mà mình nghĩ nÊn viết thêm vô là có phải lúc nào độ phức tạp nhỏ cũng xài được không?
Vd: Linear search mất O(n) và Binary search mất O(logn).
Nhìn có vẻ Binary seach nhanh hơn hẳn Linear search, tuy nhiên Binary Search chỉ áp dụng đươc khi dữ liệu được sắp xếp.
Vậy nếu dữ liệu chưa được sắp xếp thif sao? Khi đó cái nào sẽ tiện hơn?

Rồi như distribution counting sort mất O(n), tuy nhiên các giải thuật khác đều là O(n^2) -> O(nlogn) thì tại sao không dùng Distribution couting.

Cái đó về phần sorting, sẽ viết riêng 1 bài luôn.

Mà Eratosthene là O(nlogn/loglogn)

Em thấy trên wiki là O(log log n) ạ.

ủa nhầm O(n * loglogn).

A, tội lỗi quá :’( cảm ơn anh đã chỉ ạ.

Bài viết khá dễ hiểu, thích hợp cho người mới làm quen. Nếu có thể, tác giả nên viết thêm một số phương pháp tìm giới hạn chặt Big Theta. Một số cách chứng minh độ phức tạp thuật toán.

cái ví dụ O(n^3) lấy nhân ma trận bằng cách thông thường cho nó bình dân, O(2^n) thì ví dụ là sinh tất cả các tập con của 1 tập hợp. Mấy cái log log n hay n log log gì bỏ hết đi có thường gặp đâu…

Cho em hỏi, có phải để đánh giá độ phức tạp của thuật toán bất kỳ, đầu tiên chúng ta phải xem trong đó có những phép tính toán gì, sau đó từng phép tính toán có độ phức tạp riêng rồi cộng tất cả lại phải không ạ? Em xem bài rồi vẫn thấy hơi lơ mơ tí

Về nguyên tắc là vậy nhưng sẽ có trường hợp không gộp chung được (như số phép cộng và số phép nhân, hay số phép swap và so sánh). Rõ hơn thì phép cộng là O(n) còn phép nhân không phải O(n).

Hay quá, cần những bài những thế này, em khá về giải thuật, nhưng lại mù độ phức tạp