Big O Notation / 시간 복잡도 / 공간 복잡도

📝 시간 복잡도(Time Complexity)

알고리즘의 실행 속도를 의미

⚡️ 문제 풀이에 대한 방법은 여러가지가 있겠지만, 가장 실행 속도가 적은 최적의 코드를 짜는것이 효율적이므로 알고리즘을 짤 땐 이 시간 복잡도라는 것의 중요성이 높아짐

시간 복잡도의 점근 표기법

Big-O표기법 / O(N) : 빅오 표기법은 알고리즘 최악의 실행시간을 표기
Ω 표기법 / Ω(N) : 오메가 표기법은 알고리즘 최상의 실행시간을 표기
Θ 표기법 / Θ(N) : 세타 표기법은 알고리즘 평균 실행시간을 표기

🔐 Big O Notation

불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용되는 시간 복잡도 성능 표기법

성능 순서(오른쪽으로 갈수록 성능이 안좋음)

- O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n)

가장 왼쪽 O(1)으로 갈수록 실행 횟수가 적은 것 / 시간 복잡도가 낮은 것 이라 말할 수 있고, 가장 오른쪽 O(n!)으로 갈수록 실행 횟수가 많은 것 / 시간 복잡도가 높은 것

O(1) 상수 시간

: 스택의 push, pop
: 알고리즘이 입력에 관계 없이 연산이 수행된다. 즉 입력 데이터의 크기에 상관없이 일정한 시간이 걸림
: 알고리즘이 문제를 해결하는데 오직 한 단계만 거침

function BigO(n){
  console.log("Hello Big-O");
}

O(log n) 로그 타임

:Binary search tress access(이진 검색), search(검색), insertion(삽입), deletion(삭제)
: 데이터양이 많아져도, 시간이 조금씩 늘어남
: 시간에 비례하여, 탐색 가능한 데이터양이 2의 n승이 됨
: 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬
: 만약 입력 자료의 수에 따라 실행 시간이 이 log N의 관계를 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어남( 주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형)

/**
  * (1) O(log n)의 대표적인 알고리즘은 이진검색이다. 아래 정렬된 값들중에서 6이라는 값을 찾아보기로한다.
  * (2) 정렬이 되어있으니까 이진검색을 하려면 우선 가운데값인 5를 찾아서 키값과 비교한다. 
  *      즉, 키값이 가운데값인 5보다 더크므로 오른쪽에 있다. ( 이제부터 앞에 1,2,3,4,5는 제외시킨다. )
  * (3) 뒤쪽의 데이터 6,7,8,9중에 중간값인 7을 찾아서 키값과 비교한다. 키값이 더 작으니까 왼쪽(=앞쪽)에 있다고 추측할 수 있다. 
  *      (이제부터 뒤쪽에 7,8,9 데이터는 안봐도 되므로 제외시킨다.)
  * (4) 위의 과정이 끝나면 찾는값인 6이 남아있다. 
  * (5) 이렇게 한번 처리가 진행될때마다 검색해야하는 데이터의 양이 절반씩 떨어지는 알고리즘을 O(log n)알고리즘이라 한다.
*/
function(k, arr, s, e) {
    if (s > e) return-1;
    m = (s + e) / 2;  // 주어진 range에 중간값을 찾는다.
    if (arr[m] == k) return m;

    // 찾는값이 중간값보다 작으면 중간지점 바로 전까지 range를 지정해서 다시 호출
    else if (arr[m] > k) return function(k, arr, s, m-1);  

    // 찾는값이 중간값보다 크면 끝에서 다시 찾아야 하므로 가운데 번호 + 1부터 끝까지 호출하면 한번 함수가 호출될때마다
    // 중간값을 기준으로 절반은 검색영역에서 제외시켜버리기 때문에 순차검색에 비교해서 속도가 현저하게 빠르다.
    else return function(k, arr, m+1, e);   
}

O(n) 선형 시간

: 알고리즘이 입력한 개수인 n만큼 수행 -> 즉 입력 데이터가 증가할수록 처리시간도 증가
: Linear search, for 문을 통한 탐색

function BigO(n){
for(let i=0; i<n; i++){
    console.log(i);
  }
}

O(nlog n) 로그 선형 시간

:Quick Sort(빠른 정렬), Merge Sort(병합 정렬), Heap Sort(힙 정렬)
: 데이터양이 N배 많아 진다면, 실행 시간은 N배 보다 조금 더 많아짐 (정비례x)
: 이 유형은 커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타남(N이 두배로 늘어나면 실행시간은 2배보다 약간 더 많이 늘어남)

O(n^2) 2차 시간

: 알고리즘이 입력한 개수의 n^2만큼 수행 -> 즉 입력 데이터가 증가할수록 처리시간이 제곱 배로 증가(효율이 좋지 않음, 사용x)
: 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

function BigO(n){
  for(let i=0; i<n; i++){
    console.log(i);
      for(let j=0; j<n; j++){
    	console.log(j);
      }
   }
}

O(2^n) 지수 시간

: 피보나치수열과 유사
-> 바로 전 두 숫자를 더해서 다음 숫자를 만드는 패턴

/**
  * 함수를 호출할때 마다 바로 전의 숫자랑 전전 숫자를 알아야 더할 수 있기 때문에 해당 숫자를 알아내기 위하여
  * 하나 뺀 숫자를 가지고 재귀호출을하고 두개 뺀 숫자를 가지고 한 번 더 이렇게 매번 함수가 호출될 때마다
  * 두번 씩 또 호출을 하게 되는데 그걸 아래 이미지처럼 트리의 높이만큼 반복하는 것이다.
*/
function(n, r) {
    if (n <= 0) return 0;
    else if (n == 1) return r[n] = 1;
    return r[n] = function(n-1, r) + function(n-2, r);
}

---

🥨 마무리 팁

빅오에서 상수는 버림!

/**
  * 이건 n만큼씩 두번돌리니까 O(2n)만큼의 시간이 걸린다.
  * 그런데 빅오표기법에서는 O(2n) => O(n) 으로 표시한다.
  * 이유는 빅오표기법은 실제 알고리즘의 러닝타임을 측정하기 위해 만든것이 아니라 
  * 장기적으로 데이터가 증가함에 따른 처리시간의 증가율을 예측하기위해 만들어진 표기법이기 때문이다.
  * 상수는 고정된 숫자니까 증가율에 영향을 미칠때 언제나 고정된
  * 상수만큼씩만 영향을 미치게때문에 여기서 증가하지 않는 숫자는 신경쓰지 않겠다는 뜻이다.
*/
function(int[] n) {
    for i = 0 to n.length
        print i
    for i = 0 to n.length
        print i
}

/**
  * 마찬가지로 O(n^2 + n^2) => O(n^2) 이렇게 표기한다.
*/
function(int[] n) {
        for i = 0 to n.length
	    for j = 0 to n.length
	        print i + j;
        for i = 0 to n.length
	    for j = 0 to n.length
	        prit i + j;    
}

---

✂️ 공간 복잡도

공간 복잡도(Space Complexity)란 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법

• 시간과 공간은 반비례적 경향이 있음
• 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
• 알고리즘은 시간 복잡도가 중심

공간 복잡도 계산(Big-O)

a = 1 일반적으로 공간이 하나 생성되는 것을 1이라고 표현 -> O(1)로 표기

result = 0
for i in range(1, 100):
	result += i

반복문이 N번만큼 반복해도 for문 안에서의 지역변수이므로 공간 복잡도는 여전히 O(1)

• i와 result 변수만 사용
• 다른 것은 전혀 영향을 주지 않음
• 공간 복잡도도 O(1)

#재귀함수
def factorial(n):
    if n == 1:      # n이 1일 때
        return 1    # 1을 반환하고 재귀호출을 끝냄
    return n * factorial(n - 1)    # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함

함수의 매개변수 n의 값에 따라 공간 복잡도가 달라지는 경우 -> 함수 내부에서 n이 1일 때까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 공간 복잡도는 O(n)

공간 복잡도 줄이는법

공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼침

• 고정 공간
• 가변 공간 (공간 복잡도 측면에서 효율적)

함수 호출시 할당되는 지역변수들이나 동적 할당되는 객체들도 모두 공간이 필요 ->특히, 재귀 함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소를 저장할 공간이 필요해서 재귀적(Recursive)으로 짤 수도 있고, 반복문으로도 짤 수 있는 경우에는 반복문으로 짜는 것이 더 효율적

---

이게 왜 답이 O(n)인건지 이해가 아직도 안된다
이중 for문에다가 변수도 2개 선언이면 O(n^2) 아닌가...