Thỏa thuận lớn về ký hiệu Big-O trong khoa học máy tính là gì?

Question

Làm cách nào để ký hiệu Big-O giúp tôi lập trình C# hàng ngày? Nó chỉ là một bài tập học thuật?

Answer 1

Naw, tôi đã tự hỏi rằng quá, nhưng bây giờ tôi thấy mình suy nghĩ về big-O chỉ là về mỗi khi tôi sử dụng một thư viện.

Big-O cho bạn biết thời gian chạy tiệm cận của bất kỳ hàm nào, theo cách đó bạn có thể quyết định xem cấu trúc dữ liệu A có nhanh hơn cấu trúc dữ liệu B cho mục đích của bạn không. Ví dụ:

Ví dụ: bạn có thể bị cám dỗ sử dụng một cái gì đó giống như ArrayList khi những gì bạn thực sự cần là Queue. Khi bạn cố gắng thêm một phần tử vào ArrayList, nếu bạn có thể thấy rằng thời gian chạy là O(n) (vì nó cần tạo một mảng mới và sao chép tất cả các phần tử qua ... đôi khi) nhưng trong một Queue nó là O(1) thì bạn có thể dễ dàng thấy rằng hàng đợi sẽ nhanh hơn. Đây thực sự là một ví dụ kém khi có nhiều khác biệt khác giữa hai cấu trúc này, nhưng bạn có ý tưởng;)

Answer 2

Big-O cho bạn biết độ phức tạp của thuật toán về kích thước đầu vào của nó. Đây là cần thiết nếu bạn muốn biết các thuật toán sẽ mở rộng như thế nào. Nếu bạn đang thiết kế một trang web lớn và bạn có nhiều người dùng, thời gian bạn cần để xử lý các yêu cầu đó là quan trọng. Nếu bạn có rất nhiều dữ liệu và bạn muốn lưu trữ nó trong một cấu trúc, bạn cần phải biết làm thế nào để làm điều đó một cách hiệu quả nếu bạn định viết một cái gì đó mà không mất một triệu năm để chạy.

Không phải là ký hiệu Big-O chính nó sẽ giúp bạn. Đó là nếu bạn hiểu được ký hiệu Big-O, bạn hiểu được các thuật toán phức tạp nhất. Về cơ bản, Big-O mang đến cho bạn một ý thức cấp cao về thuật toán nào nhanh, chậm và sự cân bằng là gì. Tôi không thấy làm thế nào bạn có thể hiểu được ý nghĩa hiệu suất của bất cứ điều gì trong, nói, các thư viện bộ sưu tập NET nếu bạn không hiểu điều này.

Tôi sẽ không đi vào chi tiết hơn ở đây, vì câu hỏi này đã được hỏi many times, nhưng đủ để nói rằng đây là điều bạn nên hiểu. Dưới đây là một số bình chọn rất cao được đánh giá là previous Big-O question để giúp bạn bắt đầu.

Answer 3

Không, nó thực sự giúp biết hiệu quả của các thuật toán khác nhau là gì.

Nếu bạn dành thời gian để hiểu Big O, mỗi khi bạn ngồi xuống để mã hóa một vòng lặp, bạn sẽ suy nghĩ "Làm thế nào tôi có thể làm cho điều này hiệu quả hơn?" - đó là một điều tốt :)

Answer 4

Ký hiệu Big O cho phép bạn phân tích các thuật toán về hiệu quả tổng thể và khả năng mở rộng. Nó tóm tắt những khác biệt về trật tự liên tục về hiệu quả có thể thay đổi từ nền tảng, ngôn ngữ, hệ điều hành để tập trung vào hiệu quả vốn có của thuật toán và cách nó thay đổi tùy theo kích thước của đầu vào.

Answer 5

Biết điểm mạnh và điểm yếu tương đối của các loại thùng chứa và thuật toán sắp xếp khác nhau giúp bạn chọn đúng loại cho tình huống hiện tại. Ký hiệu Big O là một cách thuận tiện để thể hiện sự khác biệt lớn, độ phức tạp về thuật toán.

Answer 6

Big-O rất quan trọng trong thiết kế thuật toán nhiều lần trong ngày. Nói chung bạn không cần phải biết Big-O trừ khi bạn đang làm việc trên rất nhiều dữ liệu (nghĩa là nếu bạn cần sắp xếp một mảng có 10.000 phần tử, không phải 10). Trong rất nhiều trường hợp, chúng là những thư viện xử lý những thứ phức tạp cho bạn (giống như chức năng được xây dựng trong sort), nhưng trong một số trường hợp, bạn cần tự mình làm điều đó.

Điểm mấu chốt là Big-O khá dễ học, vì vậy, chỉ cần tìm hiểu nó. Nó sẽ giúp bạn trong một loạt các trường hợp.

Answer 7

Viết phần mềm tốt chủ yếu là về sự hiểu biết và đưa ra quyết định sáng suốt về phần bù trừ trong thiết kế của bạn. Ví dụ, đôi khi bạn có thể chịu đựng một khoảng trống bộ nhớ lớn hơn cho thời gian thực hiện nhanh hơn, đôi khi bạn có thể hy sinh thời gian thực hiện cho một dấu chân bộ nhớ nhỏ hơn và vân vân.

Ký hiệu Big-O là việc chính thức hóa các thỏa thuận này để các kỹ sư phần mềm có thể nói một ngôn ngữ chung về chúng. Bạn có thể không bao giờ phải chính thức chứng minh các đặc tính Big-O của thuật toán mà bạn thiết kế, nhưng nếu bạn không hiểu khái niệm ở mức trừu tượng, thì rất có thể bạn sẽ không tạo ra sự cân bằng tốt trong phần mềm mà bạn phát triển .

Answer 8

Big-O là phương tiện đo lường hoặc có ý nghĩa bóng đỗ xe hiệu suất của một thuật toán về thời gian. Vì vậy, nếu bất kỳ tối ưu hóa cần phải được thực hiện trong sự tôn trọng đó, big-o là một công cụ có giá trị. Nó là một chương nền tảng trong các thuật toán và các lớp cấu trúc dữ liệu. Tôi đồng ý với các thư trả lời khác đề cập rằng bạn có thể không sử dụng nó trực tiếp trong công việc lập trình hàng ngày của bạn, nhưng ngay cả mã ngày này cũng có hiệu suất có thể được đo nếu cần.

Answer 9

Tôi đang đọc câu trả lời và tôi (nghiêm túc) nghĩ rằng big-O được đánh giá thấp.

Khi lập trình viên kiếm tiền từ mã hóa, chúng tôi cần biết big-O là gì và tại sao chúng tôi cần nó.

Hãy để tôi giải thích những gì tôi nghĩ: Ký hiệu Big-O là hiệu quả/hiệu suất công việc của bạn. Bạn phải biết tốc độ mã của bạn hoạt động như thế nào khi đầu vào trở nên lớn hơn bởi vì trong thực tế, bạn không thể biết chính xác số lượng đầu vào. Hơn nữa, bạn không thể so sánh hai phương pháp tiếp cận thuật toán khác nhau mà không có ký hiệu tiệm cận vì vậy nếu bạn muốn chọn cái tốt hơn, bạn sẽ so sánh chúng với big-O và xem cái nào phù hợp với tình huống của bạn. Cả hai có thể không hiệu quả nhưng bạn sẽ biết cái nào tốt hơn.

Answer 10

Vâng, đó là chỉ một "bài tập hàn lâm". An được đảm bảo, miễn là một số học giả ngu ngốc làm bài tập như vậy bạn sẽ có thể làm một công việc lập trình tốt từ ngày này sang ngày khác :-)

Nhân tiện, nếu những học giả này không nhìn vào phép tính lambda, đồ thị lý thuyết, automatas, máy turing hoặc cái gì khác, họ tìm thấy con đường ngắn của họ để ăn tối với các nhà triết học.

Để biết thêm thông tin, có một cái nhìn tại một cuốn sách học tập tốt hoặc ít câu trả lời tuyệt vời trên ...

Answer 11

Đây là một câu hỏi mà (Hầu như) tất cả mọi người yêu cầu trong quá trình học CS của họ, đặc biệt là nếu họ có kế hoạch được các nhà phát triển công nghiệp.

Như mọi người ở đây đã chỉ ra, có, điều đó rất quan trọng. Mặc dù bạn có thể tránh được nó, hoặc không bao giờ quan tâm đến hiệu suất, tại một số điểm bạn sẽ bị ảnh hưởng bởi nó. Tại một số điểm bạn sẽ phải thao tác rất nhiều dữ liệu trong bộ nhớ, và bạn sẽ phải tìm một cách để làm điều đó một cách hiệu quả. Bạn sẽ phải lựa chọn giữa các bộ sưu tập hiện có trong một số trường hợp, và trong những người khác sẽ phải thiết kế bộ sưu tập của riêng bạn.

Điều đó đang được nói, tôi nhận thấy rằng một số trường đẩy quá nhiều khía cạnh toán học/đại số cho sinh viên đại học của họ về tầm quan trọng của việc sử dụng thế giới thực. Những sinh viên ít quan tâm đến khía cạnh đại số này sẽ phát triển một sự chán ghét. IMHO, không cần cho hầu hết sinh viên CS biết cách tính Big O ngoài những điều cơ bản.Buộc những thứ như định lý Masters xuống cổ họng của họ sẽ không làm cho họ đánh giá cao điều này.

Answer 12

Hãy nhớ rằng big-O cho bạn biết cách các thuật toán mở rộng với số lượng đầu vào lớn, nó không cho bạn biết thuật toán phù thủy nhanh hơn cho công việc của bạn.

Xây dựng kim tự tháp là O (n) trong khi sắp xếp hình ảnh của chúng là tốt nhất, O (n log n) không có nghĩa là xây dựng chúng nhanh hơn làm cho trang chiếu trượt.

Answer 13

Hãy suy nghĩ về hiệu quả, bạn của tôi!

Sự khác biệt có thể được nhìn thấy nếu sếp của bạn đang la mắng bạn để tìm địa chỉ của khách hàng theo tên của họ và bạn được cung cấp một đống giấy tờ không phân loại và sổ địa chỉ được lập chỉ mục theo tên!

Trong ký hiệu O lớn, đây là O (n) - chạy qua đống giấy không được phân loại lớn của bạn và O (1) - tra cứu chỉ mục theo tên.