알고리즘

알고리즘이란 무엇일까? 아래의 간단한 코드를 보자

max = 0
a, b, c = 10, 32, 51\
#
max = a
if max < b:
	max = b
if max < c:
	max = c
#
print(max)

위 코드는 3개의 정수 중에 하나를 임의의 최대값으로 정한 뒤,그보다 큰 정수가 나온다면 최대값을 바꿔준다.
즉, 알고리즘이란 문제를 해결하거나 혹은 해결하는 절차나 방법을 설명하는 과정으로,
컴퓨터를 활용한 문제 해결 과정에서 주어진 문제를 해결하는 일련의 방법 또는 절차 혹은,
문제해결 방법을 순서대로, 절차대로 나열한 것이라고 볼 수 있다.

빅오(O) 표기법과 시간,공간 복잡도

빅오(O) 표기법

• 프로그램(알고리즘)의 성능을 분석하는 방법들 중 하나로서 최악의 상황을 고려한 것을 나타내는 수학적인 표기법
• 표기 방법 : O(n), O(1)과 같이 알파벳 O 옆에 1 혹은 n과 같은 문자를 사용해준다.
• 종류와 예시
• O(1)

a = [3,2,1,43,16]
print(a[2])

O(1)은 알고리즘에서 입력되는 데이터에 상관없이 항상 코드의 시간 복잡도가 같을 경우
위의 코드는 입력값에 상관없이 항상 2번의 실행만으로 끝나기 때문에 O(1)로 표기

• O(logn)
  가장 대표적인 예로 재귀함수를 사용하는 2진 탐색 알고리즘이 O(logN)에 해당
• O(n)

a = [3,2,1,43,16]
for i in a:
	print(a)

• O(n^2)

a = [3, 2, 1, 43, 16]
for i in range(len(a)):
    for j in range(len(a)):
        if a[i] < a[j]:
            a[i], a[j] = a[j], a[i]
print(a)