단순 시간 복잡 도 계산
void fun(int n)
{
for(i = 0; i < n; i++)
{
printf("i = %d
", i);
}
}
:O(n)
**************************************
void fun(int n)
{
int i, j;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
printf("hello
");
}
}
}
:O(n^2)
***************************************
void fun(int n)
{
int i;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
printf("hello
");
}
}
for(i = 0; i < n; i++)
{
printf("world
");
}
}
:O(n^2)
***********************************
void fun(int n)
{
int i;
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
for(z = 0; z < n; z++)
{
printf("i = %d, j = %d
", i, j);
}
}
}
}
:T(n) = O(n^3);
: a ,T(n)= O(n^a);
:
for(i = 0; i < n-1; i++)
{
for(j = 0; j < n-i-1; j++)
{
....
}
}
**************************************************
void fun(int n)
{
int i;
for(i = 1; i < n; i *= 2)
{
printf(" , !
");
}
}
:
:T(4)= 2 T(8)= 3
n = 2^T(n) T(n) = log2n
************************************************
: T(n)=T(n-1)+n(n )
T(0)=1, :
T(n)=T(n-1)+n
T(n-1) = T(n-2)+n-1
T(n)=T(n-2)+n-1+ n
=T(n-3)+n-2 + n-1 + n
.....
=1+2+....+n
=(n*(n+1))/2
=O(n^2)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Sparse Table을 아십니까? 나는 알고 있다.Sparse Table을 지금 배웠으므로, 메모를 겸해 씁니다. 불변의 수열의 임의의 구간에 대한 최소치/최대치를, 전처리 $O(N\log N)$, 쿼리 마다 $O(1)$ 로 구하는 데이터 구조입니다. 숫자 열의 값...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.