>source

이 code 조각이 O(N^2)인지 아니면 다른 것인지 잘 모르겠습니다.

for(int i= 0; i < n; i++) {
   for(int j= i + 1; j < n; j++) {
      //stuff
   }
}

  • 답변 # 1

    네, 그렇습니다. 이것이 이 질문을 하기에 가장 좋은 장소는 아니지만, 나는 다음과 상관없이 대답하려고 노력할 것입니다.

    프로그램을 다음과 같이 생각할 수 있습니다.물건(n= 5의 경우):

    4회, 3회, 2회, 1회, 0회 총 4+3+2+1= 10회입니다.

    이것은 단순히 0에서 n-1(이 경우 4)까지의 모든 양의 정수를 더하여 총 반복 횟수를 구하는 것입니다. 이것은 n(n+1)/2 또는 (n^2 + n)/2로 모델링할 수 있습니다.

    당신이 가장 높은 차수를 취하고 나머지는 무시하기 때문에 예, 이것은 O(n^2)의 시간 복잡도를 갖습니다.

    일반적으로 시간 복잡도는 거의 예외 없이 항상 O(for 루프의 n^수)입니다.

  • 이전 다중 테넌트 애플리케이션에서 내 앱 포털 및 Azure AD SSO로 로그인
  • 다음 python : 파이썬에서 데이터 프레임의 히트 맵을 만드는 방법