[python] list에서 min(), max() 내장 함수 시간 복잡도

프로그래머스 문제 중 제일 작은 수 제거하기를  풀던 도중

정답은 나오는데 시간 초과로 케이스 1번이 자꾸 넘어가지 않는것이다. 

 

케이스1번 시관 초과로 뜬 코드는 아래의 것이다.

def solution(arr):
    arr = [i for i in arr if i != min(arr)]
    return [-1] if len(arr) == 0 else arr

 

리스트에서 최소값을 구하는 min()함수를 변수에 담아서 실행하니 넘어가는 것이 아닌가!

음, 둘의 차이가 궁금하니 찾아보자!

나처럼 케이스1번에서 넘어가지 못한 사람의 질문하기 답에서 힌트를 얻었다.

def solution(arr):
    min_number = min(arr)
    arr = [i for i in arr if i != min_number]
    return [-1] if len(arr) == 0 else arr

 

나처럼 케이스1번에서 넘어가지 못한 사람의 질문하기 답에서 힌트를 얻었다.

arr 길이의 최대값이 정해진게 없습니다. 무진장 길 수 있다는 소리죠. 그런부분에서 arr의 매 원소마다 min(arr)를 실행하는건 큰 부담이 됩니다. 시간 복잡도가 arr의 길이이기 때문이죠. min(arr)의 결과를 변수에 넣고 그걸 사용하는 코드로 바꿔보세요.

 

for문을 돌면서 계속 min() 함수를 돌리기 때문에 시간이 낭비되는군!

 

 

---

흠 그럼 리스트에서 min, max 내장 함수의 시간 복잡도를 체크해볼까?

list

The Average Case assumes parameters generated uniformly at random.

Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at both ends, consider using a collections.deque instead.

Operation	Average Case	Amortized Worst Case
Copy	O(n)	O(n)
Append[1]	O(1)	O(1)
Pop last	O(1)	O(1)
Pop intermediate[2]	O(n)	O(n)
Insert	O(n)	O(n)
Get Item	O(1)	O(1)
Set Item	O(1)	O(1)
Delete Item	O(n)	O(n)
Iteration	O(n)	O(n)
Get Slice	O(k)	O(k)
Del Slice	O(n)	O(n)
Set Slice	O(k+n)	O(k+n)
Extend[1]	O(k)	O(k)
Sort	O(n log n)	O(n log n)
Multiply	O(nk)	O(nk)
x in s	O(n)
min(s), max(s)	O(n)
Get Length	O(1)	O(1)

list에서 min,max 내장 함수의 시간 복잡도는 Big O로 표현한다면 O(n)

• 배열의 각각 아이템을 위해 모두 작업해야하기 때문에 배열이 커지면 필요 스텝도 커진다.
• 인풋⬆️ 하면 스텝도⬆️
• 선형 시간 복잡도 

---

 

따라서 처음처럼 for문 안에서 min 내장함수를 계속 돌리면 arr 길이만큼 시간 복잡도가 늘어나기 때문에

시간 초과가 날 수밖에 없었던 것이군😅

주의하자!