데이터 구조0: 복잡 도 분석

1733 단어
시간 복잡 도 원칙
  • 덧셈 원칙
    • T(n)=T1(n)+T2(n)=O(f(x))+O(g(n))=O(max(f(n),g(n)))
  • 곱셈 원칙
    • T(n)=T1(n)∗T2(n)=O(f(n)∗g(n))=O(f(n)∗g(n))
  • 점진 적 시간 복잡 도 O (1) < O (lg2n) < O (n) < O (nlgn) < O (n2) < O (n3) < O (2n) < O (n!) < O (nn)
    • 복잡 도 계산
    상수 단계
    선형 단계
    //O(n)

int i;
for(i=0;i<n;i++)
{ 
}

    대수 단계
    //O(lg2n)
int cnt=1;
while(cnt<=n)
{
   cnt=cnt*2;
}
  • 2x=n=>x=log2n

    • 평방 급
    int i,j;
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    {...}
  • O(n2) 
    • int i,j;
for(i=0;i<m;i++)
  for(j=0;j<n;j++)
    {...}
  • O(m∗n) 
    • int i,j;
for(i=0;i<n;i++)
  for(j=i;j<n;j++)
    {...}
  • n+(n−1)+...+1=n(n+1)2
  • 1+2+3+...+n=n∗n−12
  • 12+22+...+n2=n(n+1)(2n+1)6
  • 13+23+...+n3=(n(n+1)2)2

    • 전형 적 인 알고리즘 분석
    SQL2005 인덱스 재생성 저장 프로세스 sprebuild_index 오리지널
    pandas 상세 설명

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage