점근표기법

• 컴퓨터 공학자들이 시간과 공간에 관여하는 알고리즘을 나타내는 표기법이다. O(n)으로 표기한다.
• 표기법에서 나타내는 항은 가장 큰 변수를 중심으로 표시된다. 그 이유는 사소한 숫자에와의 차이에는 모든 항의 영향력이 크지만 대입되어지는 값이 10000, 1000000 이렇게 엄청 커지게 되면 자잘한 상수 보다 n의 제곱의 항의 차이가 더 크기 때문이다.
• 표시할 때 가장 큰 항을 제외한 모든 항과 가장 큰 항의 계수를 없앤다. 그리고 남은 항이 n이면 O(n)으로, n의 제곱승이면 O(n²) 이런식으로 표시한다.
• 선형 탐색은 리스트에 있는 항을 하나씩 다 대입해서 찾기 때문에 O(n)이라고 하고, 이진 탐색은 리스트의 중간값을 기준으로 탐색하기 때문에 절반으로 줄어든다. 그래서 O(logn) 으로 표시한다.

시간 복잡도

O(1) - 인풋의 크기와 소요시간이 상관없을때 이루어짐(반복문이 없으면 대체로 1 이다.)
O(n) - 반복문이 있고 반복되는 횟수가 인풋의 크기와 비례할때 표시, 만약 반복되는 횟수가 n/2번 이루어 지게 된다면 n*1/2이기 때문에 n으로 표시한다. 또한 똑같은 자리에 있는 반복문이 3개면 O(3n)이지만 n의 계수는 버리기 때문에 O(n)으로 표시한다.
O(n²) - 반복문 안에 반복문이 있을 경우 n의 제곱으로 표시한다.
O(logn) - n의 값이 증가하는 방식이 배로 증가한다거나, 1/2로 감소하면서 진행된다면 반복의 횟수는 감소하기 때문에 logn으로 표시한다.
O(nlogn) - O(n)과 O(logn)이 중복으로 되있는 경우에는 nlogn으로 표시힌다.

for i in range(n):
    j = 1
    while j < n:
        print(i j)
        J = J * 2

위의 코드에서는 for의 반복문은 O(n)이지만 while의 반복문은 n(logn) 입니다. while문이 for문 안에 중첩되어 있기 때문에 위의 시간 복잡도는 O(nlogn) 이라고 할 수 있습니다.

재귀

- 재귀적으로 문제를 푼다는 것

같은 형태의 더 작은 문제(base case)를 풀고 그 답을 이용해서 기존 문제(recursive case)를 푸는 것을 의미

반복문 vs 재귀함수

코드가 반복하기 위해서는 돌아가야될 위치를 저장해 놓는데 이를 'call stock'이라고 한다. 근데 이 재귀함수는 call stock이 너무 많이 쌓이면 작동이 되지않는다. 그래서 python에서는 call stock를 제한 해 놓았다. 반복문을 쓸 때 더 깔끔 할 수도 있고 재귀를 사용했을 때 간결할 수도 있기 때문에 상황에 맞게 더 효율적으로 사용하면 된다.

출처 - codit(알고리즘)