[PAI] 4장 빅오, 자료형

[Topic 1] 상한과 최악은 다르다

책 내용을 공부하다가 다음과 같은 개념을 보았다.

여기서 한 가지 중요한 점은 상한을 최악의 경우와 혼동하는 것인데, 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 ‘적당히 정확하게’ 표현하는 방법일 뿐, 최악의 경우나 평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이라는 점에 유의해야한다.

아니, 가장 늦게 실행될 때를 빅오(O), 즉 상한이라고 한다며?
그러면 그게 최악의 경우 아닌가? 이에 대한 구체적인 예시를 들어보자.

2018-19시즌에 시행되었던 한국프로농구 외국인 선수는 키가 2m를 넘을 수 없었다. A와 B는 이에 대한 대화를 나누는 중인데, A는 위 규정을 어렴풋이(?) 기억하고 있다. B는 위 규정에 대해 A에게 물어본다.

B : “그 때 KBL 외인들 키 제한을 얼마로 두고 뽑았더라?”
A : “음… 대략 2m 20cm 정도 내에서 뽑았을껄?

위 대화 내용을 상한과 최악의 경우에 맞춰 정리해보면,

• 상한 : 대략 2m 20cm 정도 내에서 뽑았다는 것
• 최악의 경우 : 실제 키 제한은 2m 였다는 것

이렇게 보면 최악의 경우는 상한에 포함되는 것으로 보인다.
키 제한 2m가 2m 20cm 안에 포함된다는 것이다.

만약 A가 상한을 2m 라고 말했으면 최악의 경우가 상한이 될 수는 있다.
하지만 똑같은 의미는 아니며, 어느정도 ‘적당히 정확하게’ 표현하는 방법이라는 것이다.

[Topic 2] 불변 객체와 가변 객체를 구분하는 이유

파이썬에는 불변 객체가 존재한다.
객체가 불변이라면, 다음과 같은 특징을 갖는다.

1. Thread Safe

• 어떤 함수나 변수, 혹은 객체가 여러 Thread로부터 동시에 접근이 이루어져도 프로그램 실행에 문제가 없다.

2. Improve Correctness & Clarity

• 프로그램이 종료될 때까지 값은 변하지 않는다
• 값의 수정을 고려할 필요가 없어진다

3. Mutable is harder to reason

• 같은 객체에 대해 여러 참조가 가리켜진다면 코드의 정확성을 위협한다
• 코드의 한 부분에서 값을 변화 시켰다면, 코드의 다른 부분에서 이에 대한 영향을 받는다

다음 코드가 불변 객체를 이해하는데 큰 도움이 되었다.

myList = []

for i in range(10) :
        myList.append(‘hello’)

for i in range(10) :
        print(id(myList[i]))

결과 : myList 내 원소들의 모든 주소 값들은 전부 동일하다!