Kí hiệu O lớn

Kí hiệu O lớn

Sử dụng toán học để đo mức hiệu quả của code

Đây là bài dịch của mình về kí hiệu O lớn. Bạn có thể đọc bài gốc tiếng Anh tại đây

Ý tưởng đằng sau kí hiệu O lớn

Kí hiệu O lớn là ngôn ngữ ta dùng để diễn tả một thuật toán máy tính sẽ chạy trong bao lâu. Đây là cách chúng ta so sánh mức hiệu quả của các cách tiếp cận khác nhau đối với một vấn đề.

Với kí hiệu O lớn, chúng ta diễn tả thời gian chạy theo quan điểm – thời gian chạy sẽ tăng lớn như thế nào khi dữ liệu đầu vào tăng lớn một cách tùy ý.

Phân tích một chút:

  1. Thời gian chạy sẽ tăng lớn như thế nào – Một vài yếu tố bên ngoài có tác động tới thời gian chạy của một thuật toán ( bạn có thể gọi một hàm, hoặc một cái gì khác tùy bạn) : tốc độ của bộ xử lý, máy tính có chạy chương trình gì khác hay không,… Rất khó có một kết luận chắc chắn để đưa ra thời gian chạy chính xác của một thuật toán. Thay vào đó, chúng ta sử dụng kí hiệu O lớn để diễn tả mức độ tăng lớn của thời gian chạy.
  2. khi dữ liệu đầu vào – Bởi vì chúng ta không tìm kiếm một con số chính xác, chúng ta cần miêu tả độ tăng lớn của thời gian chạy dựa vào hay tương ứng một cái gì đó. Đó chính là kích cỡ của dữ liệu đầu vào. Chúng ta có thể nói thời gian chạy tăng lên “cùng cấp độ với độ lớn của dữ liệu đầu vào” (Ο(n)) hoặc “ với cấp độ bình phương độ lớn của dữ liệu đầu vào” (Ο(n2)).
  3. tăng lớn một cách tùy ý – Thuật toán của chúng ta có những bước có vẻ như là tốn kém khi n có giá trị nhỏ nhưng giá trị của thuật toán sẽ càng lúc càng sáng tỏ khi giá trị n trở nên lớn. Đối với phân tích O lớn, ta chỉ quan tâm tới những thứ sẽ tăng lớn nhanh nhất khi dữ liệu đầu vào tăng, bởi vì những thứ khác sẽ nhanh chóng bị lu mờ khi giá trị n trở nên rất lớn. Phân tích O lớn đôi khi còn được gọi là phân tích tiệm cận.

Kí hiệu O lớn có vẻ giống như toán học ngoại trừ việc nó là một kiểu toán vô cùng thú vị và không hề nhàm chán.

Một vài ví dụ

public void PrintFirstItem(int[] arrayOfItems)
{
    Console.WriteLine(arrayOfItems[0]);
}

Thời gian chạy của hàm này là Ο(1) ( hay thời gian không đổi) tương ứng với dữ liệu đầu vào. Mảng đầu vào có thể là 1 phần tử hay 1000 phần tử, nhưng hàm này vẫn sẽ chỉ cần một lần chạy.

public void PrintAllItems(int[] arrayOfItems)
{
    foreach (var item in arrayOfItems)
    {
        Console.WriteLine(item);
    }
}

Thời gian chạy của hàm này là Ο(n) (hay là thời gian tuyến tính) , với n là số lượng phần tử của mảng đầu vào. Nếu mảng có 10 phần tử, chúng ta phải thực hiện lệnh in 10 lần. Nếu mảng có 1000 phần tử, ta cần phải in 1000 lần.

public void PrintAllPossibleOrderedPairs(int[] arrayOfItems)
{
    foreach (var firstItem in arrayOfItems)
    {
        foreach (var secondItem in arrayOfItems)
        {
            Console.WriteLine($"{firstItem}, {secondItem}");
        }
    }
}

Hàm trên chúng ta thực hiện hai vòng lặp. Nếu mảng của chúng ta có n phần tử, vòng lặp ngoài sẽ chạy n lần và vòng lặp trong sẽ chạy n lần - tương ứng với một lần chạy của mỗi vòng lặp ngoài, tổng cộng chúng ta sẽ in n2 lần. Do đó thời gian chạy của hàm này là Ο(n2) (hay thời gian bậc hai). Nếu mảng có 10 phần tử, chúng ta phải in 100 lần. Nếu mảng có 1000 phần tử, ta phải in 1,000,000 lần.

N có thể là giá trị thực sự của đầu vào, hay cũng có thể là kích thước của đầu vào

Cả hai hàm dưới đây đều có thời gian chạy là Ο(n) tương ứng với đầu vào, mặc dù đầu vào của hàm đầu tiên là một số nguyên, còn đầu vào của hàm còn lại là một mảng.

public void SayHiNTimes(int n)
{
    for (int i = 0; i < n; i++)
    {
        Console.WriteLine("hi");
    }
}
public void PrintAllItemsInArray(int[] theArray)
{
    foreach (var item in theArray)
    {
        Console.WriteLine(item);
    }
}

Do đó ta thấy đôi khi n được định nghĩa là giá trị thực sự của đầu vào của hàm, hoặc đôi khi n là số lượng phần tử của mảng đầu vào (hoặc là số lượng input map, hoặc là số lượng đối tượng đầu vào (input object),…).

Bỏ các giá trị cố định

Một luật lệ quan trọng khi phân tích O lớn là việc chúng ta sẽ loại bỏ các giá trị cố định (hằng số) khi tính toán độ phức tạp O lớn của một hàm. Ví dụ như:

public void PrintAllItemsTwice(int[] theArray)
{
    foreach (var item in theArray)
    {
        Console.WriteLine(item);
    }
     // lặp lại lần nữa
    foreach (var item in theArray)
    {
        Console.WriteLine(item);
    }
}

Thời gian chạy của hàm trên là Ο(2n), nhưng ta chỉ xem đơn giản là Ο(n) với n là giá trị độ lớn của mảng đầu vào nhân với 2.

public void PrintFirstItemThenFirstHalfThenSayHi100Times(int[] theArray)
{
    Console.WriteLine(theArray[0]);
    int middleIndex = theArray.Length / 2;
    int index = 0;
    while (index < middleIndex)
    {
        Console.WriteLine(theArray[index]);
        index++;
    }
    for (int i = 0; i < 100; i++)
    {
        Console.WriteLine("hi");
    }
}

Thời gian chạy của hàm này là Ο( 1 + n/2 + 100), ta chỉ xem là Ο(n).

Tại sao lại như vậy? Hãy nhớ rằng đối với O lớn, chúng ta phân tích điều gì sẽ xảy ra với một thuật toán khi giá trị n đầu vào trở nên rất lớn. Khi n trở nên rất lớn, việc cộng thêm 100 hoặc chia n cho 2 sẽ trở nên ít tác động hơn đến đánh giá toàn cục về độ phức tạp của thuật toán đó.

Bỏ những phần tử có mức tác động thấp hơn

Ví dụ:

public void PrintAllNumbersThenAllPairSums(int[] arrayOfNumbers)
{
    Console.WriteLine("these are the numbers:");
    foreach (var number in arrayOfNumbers)
    {
        Console.WriteLine(number);
    }
    Console.WriteLine("and these are their sums:");
    foreach (var firstNumber in arrayOfNumbers)
    {
        foreach (var secondNumber in arrayOfNumbers)
        {
            Console.WriteLine(firstNumber + secondNumber);
        }
    }
}

Thời gian chạy của chúng ta ở hàm trên là Ο(n + n2), mà chúng ta chỉ xem là O(n2). Thậm chí nếu chúng ta có thời gian chạy là Ο(n2/2 + 100n), ta vẫn xem nó là O(n2).

Một cách tương tự:

Ο(n3 + 50n2 + 10000) sẽ là Ο(n3)

O((n+30)*(n+5)) sẽ là O(n2)

Một lần nữa, chúng ta đi đến kết quả này bởi vì những phần tử có tác động thấp hơn sẽ nhanh chóng trở nên ít ý nghĩa khi giá trị n tăng rất lớn.

Ta đang nói về trường hợp xấu nhất

Thỉnh thoảng trường hợp xấu nhất thì thực sự là tệ hơn rất nhiều so với trường hợp tốt nhất.

public bool Contains(int[] haystack, int needle)
{
    // Does the haystack contain the needle?
    for (int i = 0; i < haystack.Length; i++)
    {
        if (haystack[i] == needle)
        {
            return true;
        }
    }
    return false;
}

Ở đây chúng ta có thể có 100 phần tử trong mảng haystack, nhưng phần tử đầu tiên có thể chính là needle, trong trường hợp này thì chúng ta chỉ cần trả về đúng một vòng lặp.

Nói chung, khi ta nói thời gian chạy là O(n) , ta ngụ ý đây là trường hợp xấu nhất. Nhưng chúng ta vẫn có thể diễn tả cụ thể rằng trường hợp xấu nhất là O(n) và trường hợp tốt nhất là O(1) ở thuật toán trên.

Thử thách cuối cùng : độ phức tạp của không gian dữ liệu

Thỉnh thoảng chúng ta muốn tối ưu hóa bộ nhớ thay vì thời gian. Phân tích về chi phí bộ nhớ thì rất tương tự như chi phí thời gian. Chúng ta cần nhìn vào tổng kích thước của tất cả các biến mà ta gán cho (tương ứng với kích thước đầu vào).

Bộ nhớ của hàm bên dưới là O(1) (bởi vì ta không gán bất kì biến số mới nào).

public void SayHiNTimes(int n)
{
    for (int i = 0; i < n; i++)
    {
        Console.WriteLine("hi");
    }
}

Bộ nhớ của hàm dưới là O(n) so với dữ liệu đầu vào( bởi vì kích thước của mảng hiArray sẽ thay đổi tương ứng với kích thước đầu vào).

public string[] ArrayOfHiNTimes(int n)
{
    string[] hiArray = new string[n];
    for (int i = 0; i < n; i++)
    {
        hiArray[i] = "hi";
    }
    return hiArray;
}

Thông thường, khi ra nói về độ phức tạp của không gian dữ liệu, ta đang đề cập đến không gian cộng thêm, chứ chúng ta không bao gồm phần không gian bị chiếm bởi đầu vào. Ví dụ, hàm bên dưới có bộ nhớ không đổi cho dù đầu vào có n phần tử.

public int GetLargestItem(int[] arrayOfItems)
{
    int largest = int.MinValue;
    foreach (int item in arrayOfItems)
    {
        if (item > largest)
        {
            largest = item;
        }
    }
    return largest;
}

Đôi khi cần phải có sự thỏa hiệp giữa việc tiết kiệm thời gian hay tiết kiệm không gian, bạn là người quyết định cái nào cần được tối ưu hóa.

Phân tích O lớn rất hay nhưng đôi lúc cũng không phải như vậy

Chúng ta phải tạo được thói quen để nghĩ đến độ phức tạp thời gian chạy và không gian bộ nhớ của một thuật toán. Thói quen này sẽ giúp ta nhìn thấy được những tối ưu và những vấn đề hiệu suất tiềm tàng cho một thuật toán.

Phân tích tiệm cận là một công cụ quyền năng, nhưng phải sử dụng nó một cách thông thái.

O lớn bỏ qua hằng số, nhưng đôi khi hằng số lại trở nên quan trọng. Nếu ta có một chương trình cần 5 giờ để chạy, việc tối ưu hóa bằng cách chia thời gian chạy cho 5 có thể không ảnh hưởng tới O lớn, nhưng nó vẫn giúp ta tiết kiệm được 4 giờ phải chờ đợi.

Cẩn thận với việc tối ưu hóa hấp tấp. Đôi khi việc tối ưu hóa thời gian chạy hoặc không gian bộ nhớ sẽ tác động tới khả năng đọc hoặc thời gian viết code. Đối với một khởi nghiệp, sẽ quan trọng hơn để viết code sao cho có thể dễ dàng ship sản phẩm một cách nhanh chóng hoặc để dễ hiểu sau đó, thậm chí điều này sẽ tác động tới mức hiệu quả của việc tiết kiệm thời gian chạy hay tiết kiệm bộ nhớ. Nhưng điều này không có nghĩa là các dự án khởi nghiệp không cần quan tâm tới phân tích O lớn. Một kỹ sư tốt (hoặc một dự án khởi nghiệp tốt hoặc một whatever) cần biết làm thế nào để có thể đạt được sự cân bằng giữa thời gian chạy, không gian lưu trữ, thời gian thực thi, tính bảo trì và tính khả đọc.

Bạn nên phát triển kĩ năng để nhìn được những tối ưu hóa của thời gian chạy và không gian bộ nhớ, cũng như phát triển sự thông thái để đánh giá liệu những sự tối ưu này có xứng đáng để phát triển hay không?

About Author

Chia sẻ bài viết

Leave a Comment

Your email address will not be published. Required fields are marked *