빅오, 자료형
컴퓨터과학에서 빅오(O)는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도) 과 함께 공간 복잡도가 어떻게 증가하는지를 분류하는 데 사용되며, 알고리즘의 효율성을 분석하는 데에도 유용하게 활용됩니다.
빅오(O, big-O)
는 "점근적 실행 시간(Asymptotic Running Time)"을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나입니다.시간 복잡도를 표기할 때는 입력값에 따른 알고리즘의 실행 시간의 추이만 살피게 되고 종류는 크게 다음과 같습니다.
def is_sum(a: int) -> int:
return a + 23 # 파라미터가 아무리 커도 1번의 계산만 진행된다.
def B_search(arr: List[int],target: target):
low = 0
high = len(arr) - 1;
while(low <= high):
mid = (low + high) / 2;
if arr[mid] == target:
return mid
elif arr[mid] > target:
high = mid - 1
else
low = mid + 1
return -1
# 코드가 이해되지 않는다면 쉽게 up&down 게임으로 생각하면 이해하기 쉽다.
def is_iterator_sum(n: int) -> int:
answer = 0
for num in range(a):
answer += num # n값 만큼 반복 계산
return answer
def insertion_sort(array, left=0, right=None):
if right is None:
right = len(array) - 1
# Loop from the element indicated by
# `left` until the element indicated by `right`
for i in range(left + 1, right + 1):
# This is the element we want to position in its
# correct place
key_item = array[i]
# Initialize the variable that will be used to
# find the correct position of the element referenced
# by `key_item`
j = i - 1
# Run through the list of items (the left
# portion of the array) and find the correct position
# of the element referenced by `key_item`. Do this only
# if the `key_item` is smaller than its adjacent values.
while j >= left and array[j] > key_item:
# Shift the value one position to the left
# and reposition `j` to point to the next element
# (from right to left)
array[j + 1] = array[j]
j -= 1
# When you finish shifting the elements, position
# the `key_item` in its correct location
array[j + 1] = key_item
return array
def bubble_sort(array):
n = len(array)
for i in range(n):
# Create a flag that will allow the function to
# terminate early if there's nothing left to sort
already_sorted = True
# Start looking at each item of the list one by one,
# comparing it with its adjacent value. With each
# iteration, the portion of the array that you look at
# shrinks because the remaining items have already been
# sorted.
for j in range(n - i - 1):
if array[j] > array[j + 1]:
# If the item you're looking at is greater than its
# adjacent value, then swap them
array[j], array[j + 1] = array[j + 1], array[j]
# Since you had to swap two elements,
# set the `already_sorted` flag to `False` so the
# algorithm doesn't finish prematurely
already_sorted = False
# If there were no swaps during the last iteration,
# the array is already sorted, and you can terminate
if already_sorted:
break
return array
# Function for nth Fibonacci number
def Fibonacci(n):
# Check if input is 0 then it will
# print incorrect input
if n < 0:
print("Incorrect input")
# Check if n is 0
# then it will return 0
elif n == 0:
return 0
# Check if n is 1,2
# it will return 1
elif 2 >= n:
return 1
else:
return Fibonacci(n-1) + Fibonacci(n-2)
# This code is contributed by Saket Modi
# then corrected and improved by Himanshu Kanojiya
[출처 - https://favtutor.com/blogs/depth-first-search-python]
# Using a Python dictionary to act as an adjacency list
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = set() # Set to keep track of visited nodes of graph.
def dfs(visited, graph, node): #function for dfs
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')
빅오(O)는 시간 복잡도 외에도 공간 복잡도를 표현하는 데에도 널리 쓰입니다.
또한, 알고리즘은 흔히 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느린 "시간과 공간이 트레이드오프(Space-Time Tradeoff)" 관계입니다.
예를 들어 커피머신을 충전하는데 10분, 총 10잔이 나오고 커피머신에 커피가 충전되어 있다면 10초면 커피를 마실 수 있겠지만, 운이 좋지 않아 다 떨어져 있다면 10분을 기다린 뒤에 마실 수 있습니다.
여기서 운이 좋다면 10초, 운이 좋지 않다면 10분이 걸립니다.
위를 예시로 100명의 사원이 커피를 가지러 갔다고 한다면 아무리 길어도 1,000분 정도의 시간이면 모든 사원이 커피를 마실 수 있다고 생각할 수 있습니다.
하지만 실제로 그 정도의 시간이 걸렸을까요? 아닙니다. 100명의 사원 중에서 커피를 만들어야 했던 사람은 10명뿐입니다. 따라서 이 사원들이 모두 커피를 마시는데 필요한 시간은 100분 정도를 넘지 않는다는 것을 알 수 있습니다. 다시 말하면, 각 사원이 커피를 마시기 위해서는 "평균적으로" 1분 정도의 시간이 필요하다고 결론을 내릴 수 있습니다.
[출처 - https://gazelle-and-cs.tistory.com/87]
자료형
이 외에도 어떤 자료형을 요구하는지, 이들 자료형에는 어떠한 특징이 있는지 알아보겠습니다.
bool
은 엄밀히 따지면 논리 자료형이지만, 파이썬 내부적으로 1(True)과 0(False) 으로 처리되는 int의 서브 클래스 입니다."임의 정밀도(Arbitrary-Precision)"
란?사이즈 | 1 | 1 | 1 | 3 |
---|---|---|---|---|
갑 | 437976919 | 87719511 | 107 | 123456789101112131415 |
딕셔너리(Dictionary)
입니다.my_set = {1, 2, 3}
my_dictionary = {1:'a', 2:'b', 3:'c'}
우리말로 하면 '수열'
같은 의미로, 어떤 특정 대상의 순서있는 나열을 뜻합니다.
예를 들어 str은 문자의 순서 있는 나열로 문자열을 이루는 자료형이며, list는 다양한 값들을 배열 형태의 순서 있는 나열로 구성하는 자료형입니다.
때문에 파이썬은 list라는 시퀸스 타입이 사실상 배열의 역할을 수행합니다.
시퀸스는 값을 변경할 수 없는 불변(Immutable)
[str, tuple, bytes] 과 변경이 가능한 가변(Mutable)
[list, dict] 으로 구분합니다.
a = 'abc'
id('abc')
-> 4336057456
id(a)
-> 4336057456
a = 'def'
id('def')
-> 4336933872
id(a)
-> 4336933872
변수 'a'의 값은 변경이 가능하지만, 불변이라 한 이유는 위에 코드 결과값에서 알 수 있듯이 str('abc', 'def')이 저장된 주소를 참조한 것을 변경한것 뿐이지 실제로 값을 변경한 것은 아닙니다.
a[1] = 'd'
-> TypeError: 'str' object does not support item assigment
때문에 위와같은 코드를 작성하면 타입에러가 나옵니다.
정적배열인 str과 달리 가변인 list는 자유롭게 값을 추가, 삭제할 수 있는 동적 배열입니다.
원시 타입
C 나 Java 같은 대표적인 프로그래밍 언어들은 기본적으로 "원시 타입(Primitive Type)"을 제공합니다.
특히 C 언어는 동일한 정수형이라도 크기나 부호에 따라 매우 다양한 원시 타입을 제공합니다.
원시 타입은 정확하게 메모리를 타입 크기만큼의 공간을 할당하고 그 공간을 오로지 값으로 채워 넣습니다.
만약 배열이라면 "물리 메모리(Physical Memory)"에 자료형의 크기만큼 공간을 갖는 요소가 연속된 순서로 배치되는 아래의 그림과 같은 형태가 됩니다.
원시 타입은 매우 빠른 연산이 가능합니다.
아울러 Java는 원시 타입에 대응되는 클래스 "객체(Object)"를 지원하며, 단순히 메모리에 숫자만 보관하고 있을 때는 하지 못했던 문자로 변환하거나, 진법 변환, 시프팅(Shifting)"[컴퓨터가 읽는 비트(bit)를 이동시켜 빠르게 연산하는 방법] 같은 비트 조작을 할 수 있습니다.
다만 이를 위한 여러 가지 부가 정보가 추가되므로, 메모리 점유율이 늘어다고 당연히 계산 속도 또한 감소 됩니다.
파이썬은 애초에 편리한 기능 제공에 우선순위를 둔 언어인 만큼 원시 타입을 제공하지 않으며, 느린 속도와 더 많은 메모리를 차지하더라도 훨씬 더 다양한 기능을 제공할 수 있는 객체만 지원합니다.
언어 | 지원 타입 형태 |
---|---|
C | 원시 타입 |
Java | 원시 타입, 객체 |
Python | 객체 |
클래스 | 설명 | 불변 객체 |
---|---|---|
bool | 부울 | O |
int | 정수 | O |
float | 실수 | O |
list | 리스트 | X |
tuple | 리스트와 튜플의 차이는 불변 여부이며, 이외에는 거의 동일합니다.(튜플은 불변이므로 생성할 때 설정한 값은 변경할 수 없습니다.) | O |
str | 문자 | O |
set | 중복된 값을 갖지 않는 집합 자료형 | X |
dict | 딕셔너리 | X |
- c++
int a = 10;
int &b = a;
b = 7
std::cout << a << std::endl;
-> 7
- python
a = 10
b = a
id(a), id(b)
-> 4370999104 4370999104
b = 7
id(a), id(b)
-> 4370999104 4370999008
문자나 숫자 같은 불변 객체는 값의 변경이 불가능하기 때문에 이처럼 참조 변수에서 값을 바꿀수 없지만, list와 같은 가변 객체를 참조하고 있다면 참조 변수에서 값을 변경할 수 있다.
a = [1, 2, 3]
b = a
id(a), id(b)
-> 4337584832 4337584832
b[1] = 5
a
-> [1, 5, 3]
id(a), id(b)
-> 4337584832 4337584832
a = [1, 2, 3]
a == a
-> True
a == list(a)
-> True
a is a
-> True
a is list(a)
-> False
# 값은 동일하지만 list()로 한 번 더 묶어주면, 별도의 객체로 복사가 되고 다른 ID값을 가지게 됩니다.
a == copy.deepcopy(a)
-> True
a is copy.deepcopy(a)
-> False
# copy.deepcopy()로 복사한 결과 값은 같지만 ID값은 다릅니다.
%timeit -n 100 np.std(numpy_rands)
-> 3.28 ms
%timeit -n 100 standard_deviation(rands)
-> 131 ms
- 넘파이(numpy) 배열을 이용한 표준편차 계산 시간 : 3.28밀리초
- 파이썬 리스트를 이용한 표준편차 계산 시간 : 131밀리초 // 약 40배 이상 차이