중첩 순차적는 대한 루프 복잡성

Question

이 코드에 정말로 뭔가 일을 해요

:

for(int k=0; k<n; k++) {   // n 
    for(int a=0; a<k; a++) {  // n/2 -> n (watch the a<k) 
     ...       // c 
    } 
    for(int i=0; i<n; i++) {  // n 
     for(int a=0; a<i; a++) { // n/2 -> n (watch the a<i) 
      ...      // c 
     } 
     for(int j=0; j<n; j++) { //n 
      ...      //c 
     } 
    } 
} 

은 내가 찾을려고하는 것은 복잡성입니다 ... 나는 O를 발견 (N^3) 그러나 나는이 대답을 "받아들이 길"싶지 않다. 기본적으로 (a) 루프를 2 번 제거하면 같은 복잡성이 생길 것이다./

Answer 1

그것은 여전히 ​​(n은^3) O 될 것입니다 후 : 왜 여전히 O (N^3)

그러나 실제로 그 코드는 늘 같은 실행 시간이 아마도 습관이 가까이 ..입니다 the (a)의 제거. 또한

https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity

, Big O notation with nested for loops and single for loop