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

[huynhtinh (Tynk Huynk)]

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

[Minh_Hieu2 (Minh Hiếu)]

thiệt tình là không ngờ ví dụ của bác y như trường hợp của mình. Hồi trước có nộp bài làm in dãy các số nguyên tố trong phạm vi ,mình sử dụng for i in range(2,int(number**0.5)+1) rồi bị giáo viên hỏi cái này là cái gì. Và học kì sau chọn người khác học.

[hell6w9rld (HelloWorld)]

Mình đọc bài của bạn thấy có gì đó ngược ngược, Không biết bạn nhầm lẫn hay mình nhầm
Theo những gì viết ở trên thì f(n) (trong hình mô tả đồ thị là g(n)) mới là thời gian nhiều nhất cần thiết để thực hiện thuật toán. Vì T(n) bị chặn trên bởi c*f(n) với mọi n >= n0

[noname00 (HK boy)]

Ý bạn là ngược với cái hình ở dưới?

[hell6w9rld (HelloWorld)]

Ngược chỗ T(n) và f(n), thẳng nào chặn trên thằng nào, và thằng nào là độ phức tạp ~ tương đương thời gian thực hiện nhiều nhất (trường hợp tệ nhất) của 1 hàm. Ở 3 chỗ bôi vàng thì 2 chỗ sau đúng nhưng mâu thuẫn với chỗ bôi vàng đầu tiên

[noname00 (HK boy)]

Vì f(n) bị chặn trên bởi c*f(n) với mọi n >= n0

f(n) bị chặn hay là T(n)?

[hell6w9rld (HelloWorld)]

Kí hiệu ngược nhau nên mình viết nhầm, lẫn lộn. Mình sửa lại 2 comment rồi đó

[hell6w9rld (HelloWorld)]

Tóm lại là T(n) chỉ là

hàm biểu diễn thời gian thực hiện của thuật toán

chứ không phải là

“thời gian nhiều nhất cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào cỡ n”

[noname00 (HK boy)]

OK bạn, mình sẽ sửa lại.

[hell6w9rld (HelloWorld)]

Từ ý trên nhầm thì theo mình thấy: O là kí hiệu toán học để biểu diễn độ phức tạp của 1 thuật toán A, nghĩa là biểu diễn độ lớn của c.f(n), chặn trên của hàm T(n), trường hợp tệ nhất sẽ xảy ra của thuật toán A, Chứ không phải

O (ô lớn) để mô tả độ lớn của hàm T(n)

T(n) chỉ là 1 hàm giả sử, biểu diễn thời gian thực hiện thuật toán với tập dữ liệu cỡ n. Để từ đó ta ước lượng độ lớn mà T(n) sẽ đạt được trong trường hợp xấu nhất xảy ra (chính là c.f(n))

[hell6w9rld (HelloWorld)]

Nếu bạn viết được 1 bài hoàn chỉnh ntn thì hay quá. Mình thấy đa phần tài liệu viết không đủ. Mình đọc 1 vài tài liệu thì thống kê ra được nội dung về độ phức tạp này có những phần sau

• Big O
  • là gì, để làm gì, công thúc tổng quát, diễn giải bằng đồ thị
  • các quy tắc xác định
  • các dạng độ phức tạp thường gặp
  • cách thực hiện đánh giá trên công thức toán học, tìm C và n0
  • cách thực hiện đánh giá trên code
• Big O chỉ là 1 cách đánh giá trường hợp tệ nhất. Nếu viết được thêm về Big Omega với Big Theta dùng để đánh giá trường hợp tốt nhất, trung bình thì hay quá

[noname00 (HK boy)]

Đánh giá trường hợp tốt nhất, tệ nhất và trung bình phải dựa vào bộ dữ liệu đầu vào và thuật toán nữa. Hơn nữa để đánh giá thuật toán còn phải đánh giá được độ phức tạp không gian và độ phức tạp thời gian.

VD về big Theta:

https://www.quora.com/What-is-big-Theta-notation

[rogp10]

Đọc bài nhớ lại thời viết code ảo tung nóc nhà

Bây giờ thì:

{ pseudo }
{ không nhanh lắm }

def prime_number?(n) begin
   if !n || n < 2 || (n > 2 && n.even?) return false
   else if n in [2, 3] return true
   else
      x = sqrt(n).to_i
      return [3..x].stride(2) { bước nhảy }
                   .any?(i => n % i == 0)  { sử dụng hàm làm điều kiện }
   end
end

def all_proper_divisors_list(uInteger n) begin
   if n == 0 throw InvalidArgument
   x = sqrt(n).to_i
   { range to list: O(sqrt(n)) time }
   lower_list = [1..x-1].reject!(i => n % i != 0)
   higher_list = lower_list.map_reverse(i => n/i) { O(1) mem }
   { kết quả tự động xếp tăng dần }
   return lower_list.insert!(x) + higher_list if n % x == 0 
   else lower_list + higher_list
end

def all_divisors_list(uInteger n) begin
   return all_proper_divisors_list(n) << n
end

[nguyenhuuca (Nguyen Ca)]

Có thằng nó viết bằng regular nữa chứ :v

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/'

Tìm số nguyên tố với regular expression

[rogp10]

o(n^2) time chắc luôn.

[Red_Sand (mondlicht1)]

Suggest cuốn CLRS, đi từ 3 khái niệm nền tảng:
Computation model
Rate of growth
Asymptotic notations.

[rogp10]

Computation model

Model of computation hay thế nào là O(1). À ngoài ra còn average case nữa chứ.

Một số hạn chế của RAM model: Cộng trừ nhân chia số nguyên đều được cho là O(1) time nhưng kì thực chia >> nhân > cộng trừ. Caching nói chung hỗ trợ một kiểu truy cập nhất định và với mỗi loại cache thì phân tích sẽ khác đi.

[hungaya (Hung)]

Mình nghĩ là RAM model, mình có đọc CLRS và tác giả chỉ phân tích correctness và complexity ở RAM model thôi.

Random-access machine

[rogp10]

 // S là câu lệnh, E1, E2 là các biểu thức logic và F là một phép gán
 for (E1; E2; F) {
 	S;
 }

Chỗ E1 là lệnh khởi tạo chứ nhỉ.

[noname00 (HK boy)]

Đã sửa thành công