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 n² lần. Do đó thời gian chạy của hàm này là Ο(n²) (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.

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),…).

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 đó.

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 + n²), mà chúng ta chỉ xem là O(n²). Thậm chí nếu chúng ta có thời gian chạy là Ο(n²/2 + 100n), ta vẫn xem nó là O(n²).

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

Ο(n³ + 50n² + 10000) sẽ là Ο(n³)

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

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.

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ô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.

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?