코딩 연습

이전에 알아봤던 Big-Oh Notation 의 실례들을 살펴보자. $O(1)$파이썬의 list 클래스에서는 각 리스트의 길이를 저장하고 있는 변수가 존재하여 리스트 요소 하나하나를 반복적으로 접근하여 세지 않고도 그 길이를 즉각 반환하여 준다. 이런 측면에서 본다면 리스트의 길이를 구하는 것은 $O(1)$ 에 해당된다고 할 수 있다. 또한 파이썬의 리스트는 array-based sequences 로 실행되기 때문에 각각의 요소들은 연속적인 저장 공간에 하나씩 저장이 되고, 이들은 모두 인덱스를 이용하여 직접 접근할 수 있다. 예를 들어, input_data[i] 라고 하면 input_data 라는 리스트의 인덱스 i 인 저장소의 값을 그대로 반환해 준다. 따라서 이것 역시 $O(1)$ 에 해당된다고 할..

프로그램의 실행시간을 흔히 시간복잡도(time complexity)라고 말한다. 알고리즘의 분석에 있어서 이 시간복잡도를 입력 자료의 크기 $n$ 의 함수로 나타내는 것이 일반적이다. 예를 들어, 다음과 같은 파이썬 코드가 있다고 하자. def find_max(input_data): maximum = input_data[0] for element in input_data: if element > maximum: maximum = element return maximum 위의 파이썬 코드는 리스트 형태로 주어지는 input_data 의 요소 중 그 값이 가장 큰 것을 반환하는 함수 find_max 를 나타낸다. 이때 이 코드의 실행시간은 중간에 있는 for-loop 에 가장 큰 영향을 받게 되리라는 것을 ..