[자료구조] 시간복잡도 Big-O 표기법 예제(c)

이번 시간에는 시간복잡도 big-o 예제에 대해서 알아보겠다.

시간 복잡도에 대한 개념 및 설명은 생략하겠다.

#1 O(n) 복잡도

void Func1(int n)
	for(int i = 0; i <= n; i++)
    	printf("hello jihwan!\n);    

• T(n) = n ∈ O(n)

#2 O(n) 복잡도

void Func2(int n)
	for(int i = 1; i <= n; i++) --> n
    	printf("Hello jihwan");
    for(int i = 1; 1 < 2 * n; i++) --> 2n
    	printf("hello jihwan");
    for(int i = 1; i <= 3 * n; i++) --> 3n
    	printf("hello jihwan!\n);

• T(n) = n+2n+3n = 6n ∈ O(n)

#2 O(n^2) 복잡도

void Func3(int n)
	for(int i = 1; i <= n; i++) ---> n
    	for(int j = 1; j <= n; j++) ---> n  
        	printf("hello jihwan");

• T(n) = n * n = n^2 ∈ O(n^2)

#3 O(n^2) 복잡도

void Func4(int n)
	for(int i = 1; i <= 10000 * n; i++)  -> 10000n
    	printf("hello jihwan");
    for(int i = 1; i <= n; i++) ---> n
    	for(int j = 1; j <= 2*n; j++) ---> 2n
        	printf("hello jihwan");

• T(n) = 10000n + n * 2n ∈ O(n^2)

#4 O(logn) 복잡도

void Func5(int n)
	for(int i = 1; i <= n; i=i*2) --> O(logn)
    	printf("hello jihwan!"); 
    for(int i = n; i >= 1; i /= 2) --> O(logn)
    	printf("hello jihwan!");
        

• T(n) = logn + log n == logn^2 ∈ O(log n)

#5 O(nlogm) 복잡도

void Func6(int n, int m)
	for(int i = 1; i <= n; i++) -- > n
    	for(int j = 1; j <= m; j *= 2) --> logm
        	printf("hello jihwan");

• T(n) = n * logm ∈ O(nlog m)

#6 O(n+2logm) 복잡도

void Func7(int n, int m)
	for(int i = 1; i <= n; i++) -- > n 
    	printf("hello jihwan");
    for(int i = 1; i <= n; i *= 2) --> log n
    	rintf("hello jihwan");
    for(int i = 1; i <= m; i*=2) --> log m 
    	for(int j = m; j >= 1; j/=2) --> log m
        	printf("hello jihwan"); --> logm * logm 
    for(int i = 1; i <= 10000; i++) --> 10000
    	printf("hello jihwan");

• T(n) = n + log n + 2logm + 10000
  - log n(n보다 작기 때문에 소거한다.) , 10000(상수 소거)
  -> 값 도출 n+2logm