작은 걸음 III — 프로그램으로 생각하기

데이터가 많아지면 얼마나 일할까

데이터가 많아지면 얼마나 일할까

이번에 배울 것

시간 복잡도는 데이터 개수가 늘 때 필요한 작업량이 어떻게 커지는지 나타냅니다. 실제 초 수와는 다릅니다.

실행해 보기

void small_main()
{
    Array<int> sizes = {10, 100, 1000};

    for (int i = 0; i < sizes.length(); i = i + 1)
    {
        int n = sizes[i];
        int linear = n;
        print("n = ", n, ", linear worst case = ", linear);
    }
}

순차 검색은 못 찾는 경우 원소 n개를 모두 검사합니다. n이 10, 100, 1000이면 최악의 비교 횟수도 10, 100, 1000입니다.

이런 증가를 O(n)이라고 씁니다. 이 예제는 시간을 측정하는 대신 작업량을 숫자로 보여 줍니다.

Exercise — Linear 비교 횟수

20개의 값에서 없는 값을 Linear Search한다고 생각하고 실제 comparisons를 세어 출력하세요.

void small_main()
{
    Array<int> numbers(20);
    int comparisons = 0;

    // Search for 99 and count comparisons.

    print(comparisons);
}

Hint

값을 하나 볼 때마다 comparisons를 증가시키고 끝까지 찾지 못하게 하면 됩니다.

void small_main()
{
    Array<int> numbers(20);
    int comparisons = 0;

    for (int i = 0; i < numbers.length(); i = i + 1)
    {
        comparisons = comparisons + 1;
        if (numbers[i] == 99)
            break;
    }

    print(comparisons);
}