[자료구조/코테] 시간복잡도 및 알고리즘 정리

https://www.bigocheatsheet.com/

효율적인 알고리즘 코드 작성하기

- 알고리즘이 수행을 시작하여 결과가 도출될 때까지 실행에 걸리는 시간이 짧고 연산하는 컴퓨터 내의 메모리와 같은 자원을 덜 사용하는 것이 효율적

- 같은 코드이지만 다른 효율성이 나올 수도 있음 --> 이를 개선하기 위해서는 어떠한 자료형을 쓰는가가 중요함

 case1) 

-  ArrayList와 LinkedList 추가/ 삭제를 하는 경우? ArrayList느림, LinkedList 빠름

-                     ''          인덱스 조회를 하는 경우? ArrayList 빠르지만 , LinkedList 느림 

시간 복잡도란?

- 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것

- 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타냄 

- 위의 그래프를 보니.. O(logn), O(1) 정도면 효율성이 높고, 지수승 가면 horrible 해진다고 나와 있다. 

- 시간 복잡도의 순서

  $ O<(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) $ 

 

공간 복잡도?

- 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양 

- 총 공간 요구 = 고정 공간 요구 + 가변 공간 요구

- 고정 공간?  입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수) 

- 가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 그러니까 동적으로 필요한 공간

 

 

빅-오 표기법(Big-o Notation) 이란? 

- 알고리즘의 효율성을 평가하기 위한 분석법.

- 시간 복잡도(실행시간) & 공간 복잡도(실행공간)으로 이루어짐 

- $f(n)$을 계산함으로써 , 알고리즘의 효율성 이해하기  

 

$ f(n) time $ : 필요한 시간

$ f(n) space $ : 필요한 공간 (추가적인 메모리) 

 

빅-오 표기법 규칙 

1. 계수 법칙

2. 합의 법칙

3. 곱의 법칙

4. 전이 법칙

5. 다항 법칙 

 

 

 

 

<출처> 

1. 데이터구조 우선순위 큐와 힙 

2. openparadigm.tistory.com/20  

3. medium.com/@callmedevmomo/%EC%9B%B9-%EA%B0%9C%EB%B0%9C%EC%9E%90%EB%A5%BC-%EC%9C%84%ED%95%9C-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-01-%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95-ff369f0efc1d

3.https://madplay.github.io/post/time-complexity-space-complexity

4.