점근 시간 복잡도 많은 기사 또는 답변을 읽은 후에

Question

을 읽은 후에도 함수의 점근 시간 복잡도를 결정하는 문제를 해결할 수 없습니다. 이 함수는 다음과 같이 예를 들면 다음과 같습니다

def function(n): 
    for i in range(n): 
     if i == 0: 
      for j in range(n): 
       for k in range(10000): 
        print("output") 

무엇 N로 인해 "출력"을 기록 할 것 때문에 N에 얼마나 많은 시간 점근 시간 복잡도가 될 것인가?

감사합니다.

Answer 1

예 이론

시간 복잡도는 3 개 중첩 루프가 있더라도 O(n)이어야한다.

• i 루프는 n 번 실행됩니다.

• j 루프가 실행 n 번 있지만 경우 i 0

• k 루프 10000 회 실행이지만, 일정한 인자이다. 더 나은 상황에 대해 설명하기

,의 구별하자 n_i 사이, n_j가 n 동일 모두 있는데도. 복잡성은 다음과 같습니다

O(1 * n_j * 10000 + n_i * 1) = O(10000 * n_j + n_i) = O(n_j + n_i) = O(n + n) = O(n)

출력은 10000 * n 번 인쇄해야합니다.

def function(n): 
    count = 0 
    for i in range(n): 
     if i == 0: 
      for j in range(n): 
       for k in range(10000): 
        count += 1 

당신이 n의 값이 증가함에 따라 IPython에 %timeit를 호출 할 수 있습니다 :

%timeit function(10) 
5.01 ms ± 36 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

%timeit function(100) 
50.4 ms ± 334 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 

%timeit function(1000) 
497 ms ± 1.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

%timeit function(10000) 
5.03 s ± 27.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

타임즈 %의 timeit와

점검

당신은 카운터 증가하여 print 전화를 교체하는 경우 O(n)와 완벽하게 일치하는 것 같습니다! if없는 복잡성 O(n**2) 것

변화

:

def function(n): 
    for i in range(n): 
     for j in range(n): 
      for k in range(10000): 
       print("output") 

k이 range(n)에있는 경우

복잡성은 O(n**3) 다음과 같습니다

def function(n): 
    for i in range(n): 
     for j in range(n): 
      for k in range(n): 
       print("output")