Time Complexity

Time Complexity (시간 복잡도)

문제를 해결하는데 걸리는 시간과 입력한 함수 관계를 나타낸다. 

Constant Time

names 배열에 첫 번째 요소가 있다면 요소를 print 하고 없다면 no names를 리턴하는 함수라고 했을 때 Constant  Time 은 names 배열이 10개던지 1000만 개랑 상관없이 리턴하는 시간은 똑같습니다. 

데이터의 크기와 상관없이 일정한 시간이 걸립니다.

func checkFirst(names : [String]) {
    if let first = names.first {
        print(first)
    }else{
        print("no names")
    }
}

Linear Time

names 배열의 배열 요소들을 print에 출력하는 함수라고 했을 때 배열의 개수가 증가할 때마다 값을 출력하는 속도는 일정하게 비례해서 올라간다.

데이터의 크기에 비례하여 시간이 걸립니다. 

func printNames (names : [String]) {
    for name in names {
        print(name)
    }
}

Quadratic Time

names라는 배열을 반복할 때 다시 한번 더 반복하는 함수가 있다고 할 때 배열의 개수가 증가할 때마다 값을 출력하는 속도는 제곱에 비례한다.

데이터의 크기에 제곱하여 시간이 걸립니다.

func printNames(names : [String]) {
    for _ in names {
        for name in names {
            print(name)
        }
    }
}

Logarithmic Time

특정 값을 찾기 위해 가장 낮은 값과 가장 높은 값의 중간을 찾아 찾는 값과 비교하고 다시 그 중간을 찾아 찾는 값과 비교하는 것을 반복하는 함수가 있다고 할 때 속도는 조금씩 줄어든다.

func containsUsingBinarySearch(_ value : Int) -> Bool {

    var lowerBound = 0
    var upperBound = self.count - 1
    var middle = 0
    var found = false

    while(lowerBound <= upperBound) {
        middle = (lowerBound + upperBound) / 2

        if(numbers[middle] == value) {
            found = true
            break
        } else if (numbers[middle] < value) {
            lowerBound = middle + 1
        } else {
            uppperBound = middle - 1
        }
    }
    return found
    }
}