카테고리
게시일
Dec 5, 2024
시간복잡도 예상’
Magic Number
ㅤ | ㅤ |
int(4) | 21억
210,000,000 |
long long(8) | 10^17 |
대략 1초 연산에 걸리는 시간 | 1억
100,000,000 |
그래프순회(인접행렬) | O(NE) E+간선수 |
그래프순회(리스트) | O(N^2) |
N | 최대 시간복잡도 |
5,000 | |
1,000,000 | |
10,000,000 |
int 1억개 | 512MB |
ㅤ | ㅤ |
ㅤ | ㅤ |
STL 컨테이너 시간복잡도 정리
Container | Random Access | Find | Insert/Delete | feature |
vector | 1 | n | n
맨 뒤 1 | ㅤ |
deque | 1 | n | n
앞뒤 1 | ㅤ |
list | x | n | 1 | 쓰레기? |
set | x | log n | log n | ㅤ |
map | x | log n | log n | ㅤ |
queue | ㅤ | ㅤ | 뒤 1 | ㅤ |
stack | ㅤ | ㅤ | 앞 1 | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
초기화
memset
fill
#include <algorithm> fill(a,a+n,0); //
memcpy
그냥 for문으로 복사 하는 게 제일 낫다.
정렬
sort(기본 오름차순)
sort(a,a+n); // a가 n의 길이를 가질 때 sort(v.begin(), v.end()); // v
내림차순 sort
sort(a,a+n);
수학
소수
1은 소수가 아님!!
O(sqrt(n))
시간 : O(sqrt(N))
bool isPrime(int n){ for(int j=2;j*j<=n;j++){ if(n/j==0){ return 0; break; } } return 1; }
에라토스테네스의 채 O(nloglogn)
시간 : O(NloglogN)
단점 : n만큼의 bool 배열 필요
bool p[n]; // n 보다 작은 소수들 판별 memset(p,p+n,1); p[1]=0; for(int i=2;i<n;i++){ if(!p[i]) continue; for(int j=i*i;j<n;j+=i) p[j] = 0; }
왜 for(int j=i*i;j<n;j+=i) 는 loglogN 복잡도인가?
모름
순열
조합
주의사항
함수의 스택 프레임 크기
함수의 스택 프레임 크기는 1~8MB, 함수에서 정적으로 큰 배열 할당하지 않기
큰 배열을 전역공간에
정 필요하면 heap을 쓰기
int형은 4byte, int형 100만 개가 대략 4MB