let arr= [1, 2, 3] for(let i = 0; i < arr.length; ++i) { for(let j = 0; j < i; ++j) { } }


저는 처음에 어리석은 지식으로 이중for문이니까 O(n^2)겠지 싶다가

arr의 길이가 3으로 고정되어서 for(let i = 0; i < 3; ++i)와 같은 O(1)을 갖고 그 밑의 i도 정해져있기에 상수이니까 O(1) * O(1) = O(1)이니

이 코드는 상수시간복잡도를 갖는 것인가? 감히 생각했습니다.

이런 생각을 갖고 나서 뭔가 더 헷갈려져서 ai와 구글에 도움을 받았습니다.

  • 외부나 내부의 조건 중 하나가 상수가 아닐 때: 이 경우 전체 코드의 시간 복잡도는 O(n)이 됩니다. 최종적으로 입력 크기에 선형으로 비례하는 시간이 소요됩니다.

  • 외부나 내부의 조건 둘 다 변수일 때: 이 경우 전체 코드의 시간 복잡도는 O(n^2)이 됩니다. 외부 반복문과 내부 반복문의 조건이 모두 입력 크기에 대한 반복이기 때문에 제곱 관계로 시간이 증가합니다.

  • 외부와 내부 조건 둘 다 상수일 때: 이 경우 전체 코드의 시간 복잡도는 O(1)이 됩니다. 입력 크기에 무관하게 상수 시간이 소요되기 때문에 상수 시간 복잡도입니다.


  • 이렇게 나오는데 그 챗gpt는 위의 코드는 죽었다깨도 O(n^2)라고 하는 반면 구글은 상수 시간 복잡도라고 하는 글도 있고 O(n)이라고 하는 글도 있어서 헷갈립니다 형님들... 진짜 찐뉴비 구제해주시면 안되겠습니까 ㅠㅠㅠㅠㅠ