Thời gian tuyến tính v.s. Số lần hai lần

Question

Thông thường, một số câu trả lời đề cập đến giải pháp đã cho là tuyến tính hoặc số khác là bậc hai.

Cách tạo sự khác biệt/xác định nội dung là gì?

Ai đó có thể giải thích điều này, cách dễ nhất có thể, cho những người như tôi vẫn chưa biết?

Answer 1

Phương pháp là tuyến tính khi thời gian tăng tuyến tính với số lượng yếu tố liên quan.Ví dụ: vòng lặp for in các phần tử của mảng gần như là tuyến tính:

for x in range(10): 
    print x 

vì nếu in phạm vi (100) thay vì phạm vi (10), thời gian cần để chạy là 10 lần lâu hơn. Bạn sẽ thấy rất thường được viết là O (N), nghĩa là thời gian hoặc nỗ lực tính toán để chạy thuật toán tỷ lệ với N.

Bây giờ, giả sử chúng ta muốn in các phần tử của hai cho vòng:

for x in range(10): 
    for y in range(10): 
     print x, y 

Đối với mỗi x, tôi lặp 10 lần y. Vì lý do này, toàn bộ điều đi qua 10x10 = 100 bản in (bạn có thể thấy chúng chỉ bằng cách chạy mã). Nếu thay vì sử dụng 10, tôi sử dụng 100, bây giờ phương pháp sẽ làm 100x100 = 10000. Nói cách khác, phương thức này là O (N * N) hoặc O (N²), bởi vì mỗi lần bạn tăng số lượng phần tử, nỗ lực tính toán hoặc thời gian sẽ tăng lên dưới dạng hình vuông của số điểm.

Answer 2

Chúng phải đề cập đến phức tạp thời gian chạy còn được gọi là ký hiệu Big O. Đây là một chủ đề rất lớn để giải quyết. Tôi sẽ bắt đầu với bài viết trên wikipedia: https://en.wikipedia.org/wiki/Big_O_notation

Khi tôi nghiên cứu chủ đề này, một trong những điều tôi đã học là vẽ đồ thị thời gian chạy của thuật toán với các tập dữ liệu kích thước khác nhau. Khi bạn vẽ đồ thị các kết quả, bạn sẽ thấy rằng đường thẳng hoặc đường cong có thể được phân loại thành một trong các đơn hàng tăng trưởng.

Hiểu cách phân loại độ phức tạp thời gian chạy của thuật toán sẽ cung cấp cho bạn khung để hiểu cách thuật toán của bạn sẽ mở rộng theo thời gian hoặc bộ nhớ. Nó sẽ cung cấp cho bạn sức mạnh để so sánh và phân loại các thuật toán một cách lỏng lẻo với nhau.

Tôi không có chuyên gia nhưng điều này đã giúp tôi bắt đầu giảm xuống hố thỏ.

Dưới đây là một số đơn đặt hàng tiêu biểu của sự phát triển:

• O (1) - hằng số thời gian
• O (log n) - logarit
• O (n) - Thời gian tuyến tính
• O (n^2) - bậc hai
• O (2^n) - mũ
• O (n) - thừa

Nếu bài viết wikipedia khó nuốt, tôi khuyên bạn nên xem một số bài giảng về chủ đề trên Đại học iTunes và xem xét các chủ đề phân tích thuật toán, ký hiệu big-O, cấu trúc dữ liệu và thậm chí tính toán hoạt động.

Chúc may mắn!

Answer 3

Bạn thường tranh luận về một thuật toán về kích thước đầu vào của chúng n (nếu đầu vào là một mảng hoặc danh sách). Một giải pháp tuyến tính cho một vấn đề sẽ là một thuật toán mà thời gian thực hiện quy mô tuyến tính với n, vì vậy x*n + y, trong đó x và y là các số thực. n xuất hiện với số mũ cao nhất là 1: n = n^1.

Với giải pháp bậc hai, n xuất hiện trong cụm từ có 2 là số mũ cao nhất, ví dụ: x*n^2 + y*n + z.

Đối với tùy ý n, giải pháp tuyến tính tăng lên trong thời gian thực thi chậm hơn nhiều so với phương trình bậc hai.

Để biết thông tin về mor, tra cứu Big O Notation.

Answer 4

Bạn không chỉ định nhưng khi bạn đề cập đến giải pháp , có thể bạn đang hỏi về hội tụ bậc hai và tuyến tính. Để kết thúc này, nếu bạn có một thuật toán đó là lặp đi lặp lại và tạo ra một chuỗi các xấp xỉ đến một giá trị hội tụ, sau đó bạn phải hội tụ bậc hai khi bạn có thể chứng minh rằng

x(n) <= c * x(n-1)^2 

đối với một số dương tính liên tục c. Đó là để nói rằng lỗi trong giải pháp tại iteration n+1 nhỏ hơn bình phương của lỗi tại iteration n. Xem phần này để có phần giới thiệu đầy đủ hơn cho các định nghĩa tỷ lệ hội tụ chung hơn http://en.wikipedia.org/wiki/Rate_of_convergence