알고리즘의 효율성
시간 복잡도 (가장 중요하게 생각 )
알고리즘 수행 속도가 얼마나 빠르냐
//입력이 n일때 연산횟수
알고리즘 속도 비교시 입력을 똑같이 n이라고 가정 후
연산 횟수가 얼마나 되는지 알아보는것이 Big O
공간 복잡도
메모리를 얼마나 사용하고 있느냐
Big-O notation ( 대문자 O 표기법)
알고리증 성능 수학적 표현 표기법
시간, 공간 복잡도 표현
장기적으로 데이터 증가에 따른 알고리즘 성능 예측하는것이 목표
* 상수는 과감하게 버린다
// 상수는 고정된 숫자라서 , 고정된 상수 만큼의 영향만 끼치기 때문에
속도 비교
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
// ~ n lon n까지 괜찮다고 생각
//n²~ 안좋다
O(1)
입력 데이터 상관없이 항상 일정한 시간
//데이터 증가에따른 성능 변함이 없다.
배열에서 값을 찾을 때, 어느 쪽에서 시작할지를 알고 있으면 검색하는 시간이 두배로 줄어듭니다.
ex) 다수의 아이템 유무와 상관X, 하나의 인덱스에 접근
Push, pop, hash Table
O(log n)
입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
배열에서 값을 찾을 때, 어느 쪽에서 시작할지를 알고 있으면 검색하는 시간이 두배로 줄어듭니다.
ex) binary Search
//데이터 증가에도 처리가 큰 차이 안남
O(n)
입력 데이터 크기에 비례해서 처리시간이 걸림
//데이터 증가에 따라 처리시간이 같은 비율로 증가
문제를 해결하기 위한 단계의 수와 입력값 n이 1:1
// n이 10 이 들어옴 => 10번 계산
ex) 배열 요소 모두 출력
O(n log n)
ex) 퀵소트
O(n²)
문제를 해결하기 위한 단계의 수가 입력값 n의 제곱입니다.
= >입력값 n의 제곱 for문 2개 ,n길이로 2번 돌릴때
//데이터 증가에따라 처리시간 수직 상승
ex) 버블소트
O(nm)
ex) for문 m을 n만큼 돌림
//데이터 증가에따라 처리시간 수직 상승
O(n3)
ex) for 문3개, n의 길이로 3번 돌릴때
//데이터 증가에따라 처리시간 수직 상승
//가로세로 높이까지 더해져 더 급격히 처리시간 걸림
O(2ⁿ)
Fibonacci
알고리즘의 효율성
참고자료
https://joshuajangblog.wordpress.com/tag/%EB%B9%85%EC%98%A4-%EA%B3%84%EC%82%B0/