Algorithm

알고리즘

• 알고리즘이란 어떤 문제를 해결하기 위한(탕수육을 먹기위한) 방법(1,2번 조리법)이다.

A는 탕수육을 만들어 먹을것이고 조리법은 2가지이며, 두가지 조리법 중 1개의 조리법만 선택한다.

1번

1. 고기를 3번 튀긴다
2. 탕수육에 소스를 부어 담는다.(접시가 1개 사용된다)


2번

1. 고기를 1번 튀긴다.
2. 탕수육과 소스를 따로 담는다.(접시가 2개 사용된다)

A는 탕수육을 먹기 위해서 조리법(알고리즘)을 선택할 것이다. A는 조리에 걸리는 시간(= 탕수육을 튀기는 횟수)과 음식을 담는접시의 갯수를 기준으로하여 효율적인 조리법을 선택하려고 한다. 그렇다면 A에게 어떤 방법이 효율적인 조리법(알고리즘)이며, 그것을 어떻게 표현해야 할까?

효율적인 알고리즘을 선택하기 위한 방법은 2가지 방법은 시간복잡도와 공간복잡도이며 빅오표기법으로 표현한다.

시간복잡도

• 알고리즘이 어떤 문제를 해결하는 데 소요되는 연산횟수를 의미한다. 시간 복잡도가 작을수록(고기를 튀기는 횟수가 적을수록)효율적이다.

• 탕수육을 튀기는 횟수가 줄어들수록 요리에 소모되는 시간이 짧아진다. 즉 시간복잡도 측면에서 2번이 1번보다 효율적이다.

공간복잡도

• 프로그램을 실행시킨 후 완료하는 데 필요한 메모리(접시)의 양이다. 메모리가 적게 필요할수록(접시가 적게 필요할수록) 효율적이다.

• 1번은 접시가 1개 필요하지만 2번은 접시가 2개 필요하다. 즉 공간복잡도 측면에서 1번이 2번보다 효율적이다.

• 요즘에는 기술의 발달로 메모리의 여유공간이 충분하다. 따라서 공간복잡도의 중요성이 낮아져 대부분 시간복잡도를 우선시한다.

빅오 표기법

• 알고리즘의 성능을 수학적으로 표현해주는 표기법이다. 이 방법으로 알고리즘의 시간복잡도와 공간복잡도를 표현할 수 있다.

• 알고리즘의 실제 러닝타임을 표현해주는 것이 아니라 데이터나 사용자의 증가에 따른 알고리즘의 성능을 예측하는 것이 목표이다.

• O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) (오른쪽으로 갈수록 효율성이 떨어진다.)

O(1)

• 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다.

• n에 어떤크기의 값이 들어가도 연산은 1번밖에 진행되지 않아 항상 일정한 시간이 걸린다.

    def bigo(n):
      return n + 1

    print(bigo(1))

O(log n)

• 데이터 수의 증가율에 비해서 연산횟수 증가율이 매우 낮은 알고리즘

• 대표적으로 이진탐색 알고리즘이 있다.

O(n)

• 입력데이터의 크기와 연산횟수가 정비례하는 알고리즘이다.

• n이 클수록 시간이 더 많이 소요된다.

    n = [1, 2, 3]

    for i in range(len(n))
      print(i)

O(n log n)

• 데이터 수가 2배로 늘어난다면, 연산횟수는 2배조금 넘게 증가한다.

• 대표적으로 정렬 알고리즘이 있다.

O(n²)

• 입력데이터의 크기와 연산횟수가 제곱에 비례하는 알고리즘이다.

• O(n)보다 소요되는 시간이 많이 증가한다.

    n = [1, 2, 3, 4, 5]

    for i in range(len(n)):
      for j in range(len(n)):
        print(i + j)

O(n³)

• 입력데이터의 크기와 연산횟수가 세제곱에 비례하는 알고리즘이다.

    n = [1, 2, 3, 4, 5]

    for i in range(len(n)):
      for j in range(len(n)):
        for k in range(len(n)):
          print(i + j + k)

O(2ⁿ)

• 지수적으로 연산횟수가 엄청나게 증가하므로 다른 방법을 찾는것이 좋다.

• 대표적인 알고리즘의 예는 피보나치 수열이 있다.