Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- webpack
- @debug
- 자료구조
- 자바스크립트
- HTMLFormElement
- incentive
- 다중서명계약
- 해쉬테이블
- TypeScript
- goerli
- scss
- wallet
- keccak256
- currentTarget
- 블록체인
- next.js
- S3
- 스마트컨트랙트
- Sass
- set-cookie
- geth
- JavaScript
- 코딩테스트
- next-connect
- Codestates
- Goerlifaucet
- Blockchain
- CA불러오기
- ts-loader
- methoidID
Archives
- Today
- Total
Minwook’s portfolio
시간복잡도, Big O 표기법 본문
시간복잡도란? 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도
Big O 표기법, 성능비교를 위한 상대적인 표기법 중 하나
빠름 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) 느림
n이 1024라고 가정하였을때
O(n)은 1024번 루프
O(logn)은 10번 루프
즉, 상수시간에 가까울수록 시간을 대폭 절약하여 성능향상을 시킬 수 있다.
*CS에서 log 밑에 생략되어 있으면 보통 2
O(1) 상수시간
O(logn) 로그시간
O(n) 선형시간
O(nlogn) 선형로그시간
O(n^2) 이차시간
O(2^n) 지수시간
O(n!) 팩토리얼시간
//O(n)일때
for(let i=0; i<n; i+=1) {
}
//O(log n)일때
for(let i=1; i<=n; i*=2) {
}
//O(nlog n)일때
for(let i=0; i<n; i+=1) {
for(let j=0; j<=n; j*=2) {
}
}
//O(n^2)일때
for(let i=0; i<n; i+=1) {
for(let j=0; j<n; j+=1) {
}
}
4가지 법칙
1. 계수법칙 상수k가 0보다 크면 생략할 수 있다.(n이 무한에 가까워질수록 k의 영향이 적어짐)
ex) O(6n) => O(n)
2. 합의 법칙
ex) O(n) + O(m) = O(n+m)
3. 곱의 법칙
ex) O(n) * O(m) = O(nm) , O(n) * O(n) = O(n^2)
4. 다항 법칙
ex) O(6n+3m) => O(n+m) , 상수항은 무시된다.
O(n^2 + n) => O(n^2) 가장 큰 항외에는 무시된다.
성능측정방법
console.log("Start!!!!");
const start = new Date().getTime();
function(){
}
const end = new Date().getTime();
console.log(end - start);
console.log("Finish");
//console.time()을 활용한 방법
console.time("example");
function(){
}
console.timeEnd("example");
'Today I Learned' 카테고리의 다른 글
Hashtable 정리 (0) | 2022.12.28 |
---|---|
배열(Array) 정리 (0) | 2022.12.26 |
Express에서 next()의 기능분석 및 에러처리방법 (0) | 2022.10.17 |
node version 관리 및 npm install option (0) | 2022.08.31 |
HTTP header CORS 설정 (1) | 2022.08.27 |
Comments