Big O (3)

📚 Different Terms for Inputs

def print_items(a, b) :
	for i in range(a):
    	print(i)
	for j in range(b):
    	print(j)

• 이전에 봤던 O(2n)에 경우와는 다르게, 위에 함수는 두 개의 파라메터를 가지고 있기 때문에, 위와 같은 경우는 O(a + b)로 최대한 단순화 할 수 있다.

def print_items(a, b) :
	for i in range(a):
		for j in range(b):
    		print(i, j)

• 위 같은 경우도, 서로 다른 파라메터가 두 개 주어졌기에, O(n^2)로 표시하는게 아니라 O(a * b)로 단순화 해야 한다.

📚 Big O of Lists

💡 (리스트) 추가, 제거시에 Big O

• my_list = [11, 3, 23, 7]
  • 1. my_list.append(15) -> 4번 인덱스에 15가 추가됨. 즉 O(1)
  • 2. my_list.pop() -> 4번 인덱스였던 15가 제거됨. 즉 O(1)
  • 3. my_list.pop(0) -> 0번 인덱스인 11이 제거됨, 그러나 이 경우 해방 배열에는 0번 인덱스가 비어있기에 나머지 인덱스들을 다시 인덱싱해주어야 한다. 즉 O(n)
  • 4. my_list.insert(0, 11) -> 0번 인덱스에 11이 추가됨, 그러나 이 경우 이미 0번 인덱스에 다른 값이 있기에 인덱스들을 다시 인덱싱해주어야 한다. 즉 O(n)
  • 5. my_list.insert(1, 'hi') -> 1번 인덱스에 'hi'가 추가되고, 나머지 인덱스들을 다시 인덱싱해주어야 한다. 즉 O(n)

💡 (리스트) 리스트 내 항목을 값으로 탐색시에 Big O

• my_list = [11, 3, 23, 7]
  • 배열을 iterate해서 값을 찾을 경우, 배열의 크기만큼 돌아야 한다. 그러므로 O(n)
  • 인덱스를 기반으로 값을 찾을 경우는 메모리로 바로 접근이 가능하므로, O(1)

• 🗣️ (참고) n은 배열에 있는 원소에 갯수

📚 Big O < wrap up >

💡 n = 100 일때 각 Big O 요소별 소요 시간

• O(1) = 1
• O(log n) = approx 7
• O(n) = 100
• O(n^2) = 10,000

💡 n = 1,000 일때 각 Big O 요소별 소요 시간

• O(1) = 1
• O(log n) = approx 10
• O(n) = 1,000
• O(n^2) = 1,000,000

💡 Big O 요소별 용어 정리

• O(1) = constant
• O(log n) = divide and conquer
• O(n) = proportional
• O(n^2) = loop within a loop

🗣️ Big O, 시간/공간 복잡도, 정렬 알고리즘에 대해 정리가 잘 되어 있는 웹사이트
https://www.bigocheatsheet.com/