28
4
Bản thân phân tích độ phức tạp là một nội dung rất mang tính lý thuyết. Trong khoa học máy tính, có một chuyên ngành gọi là - lý thuyết độ phức tạp tính toán.
Nhiều trẻ em đã đọc "Giới thiệu về thuật toán". Cuốn sách này nhấn mạnh nhiều vào phần giới thiệu về thuật toán.
Nhưng thực tế, đối với những lập trình viên bình thường, không cần quá đề cao nội dung lý thuyết. Bởi vì hầu hết công việc là về công nghệ phần mềm thực tế nên công việc kỹ thuật không yêu cầu quá nhiều nội dung lý thuyết.
Vai trò của phân tích độ phức tạp: thể hiện hiệu suất của thuật toán.
Đối với cùng một nhiệm vụ, có thể có nhiều cách triển khai, tức là có nhiều thuật toán. Có sự khác biệt nào về hiệu suất thời gian của các thuật toán khác nhau này không?
Mặc dù chúng ta có thể sử dụng một trường hợp thử nghiệm hoặc một tập hợp các trường hợp thử nghiệm để thực sự so sánh sự khác biệt về hiệu suất. Tuy nhiên, kết quả so sánh như vậy có những hạn chế.
Ví dụ, cần đảm bảo hiệu năng của các thiết bị phần cứng máy tính chạy các thuật toán khác nhau là nhất quán, và sâu hơn nữa là trạng thái hệ điều hành của chúng tại thời điểm đó cũng cần phải nhất quán. Bản thân điều này khó có thể đảm bảo và kết quả thử nghiệm cũng liên quan đến thiết kế trường hợp thử nghiệm và đầu vào trường hợp sử dụng của chúng tôi.
Và quan trọng nhất, những so sánh như vậy được thực hiện trên thực tế.
Làm thế nào để vượt qua những hạn chế và làm thế nào để so sánh trước? Những nhu cầu khác nhau như vậy đòi hỏi chúng ta phải có một bộ công cụ để đánh giá hiệu suất của thuật toán từ cấp độ toán học và theo cách trừu tượng.
Để đáp ứng nhu cầu đó, khái niệm phân tích độ phức tạp đã ra đời.
Phân tích độ phức tạp, làm thế nào để thể hiện hiệu suất của thuật toán?
Điều quan trọng cần lưu ý là phân tích độ phức tạp của thuật toán thường xem xét trường hợp xấu nhất.
Kiểu suy nghĩ này rất phổ biến, chẳng hạn, khi bạn đi làm, để không bị trễ, bạn tính đến thời gian lâu nhất và thậm chí còn tính đến thời gian tắc đường.
Nghĩa là, phân tích độ phức tạp thể hiện giới hạn trên của hoạt động của thuật toán.
Đối với mã phương pháp tìm kiếm tuyến tính của chúng tôi, hãy tiến hành phân tích độ phức tạp. Mã được đăng lại:
Trung tâm cá nhân
Điều phát hành
từ bỏ
public static int search(E [] data,E target){ cho (int i = 0; i < data.length; i++) nếu (data[i].equals(target)) trả về i; trả về -1; }
Quá trình phân tích cụ thể như sau: n = data.length T nghĩa là mối quan hệ giữa thời gian T và n là gì? T=n?n phần tử đã được quét hết chưa? Phải không? T = 2n? Nếu có so sánh if và có kết quả trả về thì hai bước này là 2n? T = 3n? Trên thực tế, data[i] trong if, để tìm phần tử i trong dữ liệu mảng, là cách đánh địa chỉ một bước và nó cũng cần được tính là một bước phụ. 3n? T = 4n? Vòng lặp for cũng chứa những việc cần thực hiện mỗi lần, i
T = 5n? Ngoài ra còn có thao tác i++ trong vòng lặp for, vậy 5n? int i =0; cộng 1 lần, trả về -1; vậy T=5n+2? ….
Trên thực tế, nếu tiếp tục phân tích, chúng ta vẫn có thể phân tích được nhiều khả năng, vì vậy tại sao không tiếp tục?
Vì nếu thực sự phân tích thì lấy ra đoạn mã hợp ngữ tương ứng với vòng lặp for và xem vòng lặp này thực hiện bao nhiêu lệnh?
Nhưng lấy mã hợp ngữ ra là chưa đủ, vì mã hợp ngữ tương ứng với các lệnh của máy, và các lệnh của máy không chỉ là về việc có bao nhiêu dòng mã mà còn truy ngược lại kiến trúc CPU chạy mã đó. một lệnh trên một số CPU, nhưng trên một số CPU khác, nó có thể là nhiều lệnh.
Đối với các nhà phát triển phần mềm ứng dụng cấp cao, rất khó hoặc thậm chí không thể phân tích rõ ràng mỗi dòng mã ngôn ngữ cấp cao tương ứng với bao nhiêu lệnh máy. Trên thực tế, điều đó là không cần thiết.
Và ngay cả khi T=5n+2 thì đơn vị thời gian của phương trình này là bao nhiêu? Có phải là mili giây không? Nó chắc chắn không tương ứng với thời gian, nó tương ứng với số lượng lệnh, nhưng chúng ta có biết phải mất bao lâu để một lệnh được thực thi trong CPU không?
Chúng tôi không biết.
Vì vậy, chúng ta thực sự không cần phải xem xét những điều này, chúng ta cần đơn giản hóa. Đây là điều mà các nhà khoa học máy tính đã làm khi họ xác định khái niệm phân tích độ phức tạp và vâng, họ đã đơn giản hóa nó.
Chúng ta không cần biết mỗi chu kỳ cần thực hiện bao nhiêu lệnh để thực hiện một vòng lặp như vậy và hoạt động trên n phần tử; chúng ta chỉ cần biết rằng toàn bộ thuật toán và kích thước của mảng dữ liệu tỷ lệ thuận với kích thước dữ liệu n, tức là Can.
Điều này được ghi lại là O(n), biểu thị mối quan hệ tỷ lệ giữa thời gian chạy và kích thước dữ liệu n. Nhìn xa hơn, nếu: T = c1*n + c2, chúng ta có thể ghi lại thuật toán này là O(n), nghĩa là các hằng số c1 và c2 đã bị chúng ta bỏ qua, nghĩa là trong thế giới phức tạp của thuật toán, các hằng số không quan trọng.
Độ phức tạp mô tả xu hướng thay đổi của hiệu suất thuật toán khi kích thước dữ liệu tăng lên.
Giả sử có 2 thuật toán là T1 và T2 chi tiết như sau:
T1 = 10000n T2 = 2n2 Thuật toán đầu tiên là thuật toán cấp O(n) và thuật toán thứ hai là thuật toán cấp O(n2). Từ góc độ lý thuyết phức tạp, thuật toán đầu tiên tốt hơn thuật toán thứ hai.
**Vì sẽ luôn có một điểm tới hạn nào đó n0, khi n>n0, T1
Vì vậy, O(n) mô tả xu hướng thay đổi hiệu suất của thuật toán khi n thay đổi.
Thay vì nói về hiệu năng của thuật toán khi n nhận một giá trị nào đó.
Trên thực tế, nếu dữ liệu thử nghiệm nhỏ hơn 5000, chẳng hạn như 100, thuật toán thứ hai O(n²) sẽ tốt hơn thuật toán thứ nhất O(n);
Nhưng để đánh giá hiệu năng của thuật toán, chúng ta cần xét trường hợp n tăng dần hoặc thậm chí khi n là vô hạn.
Cuối cùng, bài viết này về việc đặt nền tảng vững chắc cho các thuật toán cấu trúc dữ liệu và không bao giờ sợ loạt bài phỏng vấn thuật toán 007week0102-07 Phân tích độ phức tạp đơn giản sẽ kết thúc tại đây. Chuỗi bài phỏng vấn sợ thuật toán 007week0102-07 Về nội dung phân tích độ phức tạp đơn giản, vui lòng tìm kiếm các bài viết về CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .
28
4
0
Giới hạn hiện tại của cửa sổ trượt Giới hạn hiện tại của cửa sổ trượt là một thuật toán giới hạn hiện tại được sử dụng phổ biến. Bằng cách duy trì một cửa sổ có kích thước cố định, số lượng yêu cầu được phép truyền trong một đơn vị thời gian không vượt quá ngưỡng đã đặt. Cụ thể, thuật toán giới hạn dòng cửa sổ trượt thường bao gồm các bước sau: Khởi tạo: Thiết lập cửa sổ
Đánh giá biểu thức: một biểu thức chỉ có +,-,*,/, không có dấu ngoặc đơn Một cách kỳ diệu: sử dụng một mảng để lưu trữ các số và toán tử, trước tiên tính toán phép nhân và phép chia với mức độ ưu tiên cao, sau đó tính tổng cộng Phép trừ int GetVal. (chuỗi s){
[Thuật toán] Câu hỏi về Tổng tiền tố Trước tiên, hãy xem xét một câu hỏi: (Câu hỏi về tiền tố và mẫu) Cho một mảng A[], bây giờ chúng ta muốn tìm tổng của một số số trong đó. Định dạng đầu vào: Đầu tiên có các số nguyên N, M, tức là có tổng cộng N số, có M nhóm truy vấn, sau đó có N số, tức là A[1]..
1. Để duyệt thứ tự trước theo thứ tự gốc-trái-phải, bạn có thể sử dụng đệ quy void preOrder(Node *u){ if(u==NULL)return;
Đầu tiên hãy nhìn vào câu hỏi. Đồ vật không thể tách rời mà phải mang đi hoặc để lại. Vì vậy, nó được gọi là ba lô 01 (chỉ có hai trạng thái: không lấy và không lấy). 4 món đồ vào một chiếc ba lô có sức chứa 10 Chúng ta có thể đơn giản hóa bài toán và phân tích trọng lượng từ nhỏ đến lớn
Gần đây tôi đã gặp phải vấn đề này trong một cuộc phỏng vấn: Cho ma trận sau: [[ RRRRRR], [ RBBBRR], [ BRRRBB], [ RBRRRR]] tìm nếu có
Tôi đang cố gắng gửi email qua thuật toán C++ từ tài khoản Outlook của mình, tài khoản này đã được mở và ghi nhật ký nhưng thực sự không biết bắt đầu từ đâu (để tích hợp Outlook-C++) và Google không giúp tôi nhiều đến vậy . Mọi lời khuyên sẽ được đánh giá rất cao.
Tôi thấy mình đang viết một vòng lặp while thủ công như thế này: std::list foo; // Trong trường hợp của tôi, bản đồ, nhưng danh sách thì đơn giản hơn auto currentPoin;
Tôi có mã opencv để phát hiện hình vuông. Bây giờ tôi muốn mã chạy lệnh khác sau khi phát hiện hình vuông. Mã như sau: #include "cv.h" #include "cxcore.h" #include "high
Tôi đang cố gắng mô phỏng hàm matlab "imfill" để điền vào hình ảnh nhị phân (ma trận 2D gồm 1 và 0). Tôi muốn chỉ định điểm bắt đầu trong ma trận và thực hiện tràn ngập giống như phiên bản 4 kết nối của imfill. cái này đã tồn tại ở chưa
Tôi đang đọc "Thuật toán trong C++" của Robert Sedgewick. Phần lặp lại cơ bản được đề cập là Lần lặp lại này xuất hiện trong đầu vào vòng lặp để loại bỏ sự lặp lại của một mục
Tôi đang suy nghĩ về cách tạo cấu trúc dữ liệu thể hiện các nhiệm vụ trong lịch của tôi (chỉ dành cho mục đích sử dụng cá nhân của tôi). Tôi có các bản ghi nhiệm vụ từ DBMS được sắp xếp theo ngày như sau: Mua sữa (18/1/2013) Ngày nhiệm vụ (15/01/2013) Thẻ nhiệm vụ (
Chỉ nhập một mảng số nguyên chưa được sắp xếp A[1..n] O(d): (d int) đếm số lần mỗi phần tử xuất hiện trong danh sách trong một lần lặp. bản đồ là Cây tìm kiếm nhị phân cân bằng dựa trên việc đảm bảo O(nl
Tôi có một vấn đề nhưng tôi vẫn không biết làm thế nào để giải quyết nó. Tôi đã tìm ra cách thực hiện nó một cách mạnh mẽ, nhưng nó không hiệu quả khi có hàng nghìn phần tử. Vấn đề: Giả sử bạn được cung cấp những điều sau đây
Tôi có một danh sách các danh sách. L1= [[...][...][.....].....] Nếu tôi nhận được tất cả các phần tử và trích xuất các giá trị duy nhất từ chúng sau khi làm phẳng danh sách, thì tôi nhận được Danh sách A L2 . Tôi có một danh sách L3 khác là một số L2
Chúng ta nhận được một mảng ma trận 2D (giả sử chiều dài i và chiều rộng j) và một số nguyên k, chúng ta phải tìm kích thước của hình chữ nhật nhỏ nhất chứa tổng này hoặc lớn hơn Fe k=7 4 1 1 1 1 1 4 4 Câu trả lời là 2 vì 4+4=8 >= 7,
Tôi triển khai hệ thống đảo ngược 3 danh mục và thay đổi danh mục mỗi tuần. Thứ tự là lớp buổi sáng (m), lớp buổi tối (n) và lớp buổi chiều (a). Tôi có một đơn hàng cố định không bao giờ thay đổi, ngay cả khi tôi không làm việc trong tuần đó. Tôi đã tạo một hàm để lấy số tuần ISO. Khi tôi cho nó một cuộc hẹn hò
Giả sử chúng ta có một đầu vào là danh sách các phần tử: {a, b, c, d, e, f} và các bộ khác nhau có thể chứa bất kỳ sự kết hợp nào của các phần tử này hoặc có thể chứa các phần tử khác không có trong danh sách đầu vào : A:{e,f} B:{d,f,a} C:
Tôi có thuật toán tập hợp con tìm tất cả các tập hợp con của một tập hợp nhất định. Vấn đề với tập hợp ban đầu là nó là một tập hợp đang phát triển và nếu các phần tử được thêm vào nó, tôi cần phải tính toán lại các tập hợp con của nó. Có cách nào để tối ưu hóa thuật toán tập hợp con bắt đầu lại từ điểm tính toán cuối cùng không
Tôi có một bảng chứa 1 triệu ký hiệu và tần số dự kiến của chúng. Tôi muốn nén một chuỗi các ký hiệu này bằng cách gán cho mỗi ký hiệu một chuỗi bit có độ dài thay đổi duy nhất (và có tiền tố), sau đó ghép chúng lại với nhau để thể hiện chuỗi. Tôi muốn phân bổ các chuỗi bit này để chuỗi được mã hóa trước
Tôi là một lập trình viên xuất sắc, rất giỏi!