시간복잡도가O(N^2)이라고 생각 되서 시간이 초과될거같은데 오류... - 인프런

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

import java.util.Arrays;
import java.util.Scanner;

public class lecture27 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);

        int n=scanner.nextInt();
        int m=scanner.nextInt();
        int []arr=new int[n];
        for (int i = 0; i <n ; i++) {
            arr[i]=scanner.nextInt();
        }

        int count=0;
        for (int i = 0; i <n ; i++) {
            int sum=arr[i];
            for (int j = i+1; j <n ; j++) {
                sum=sum+arr[j];
                if(sum==m)
                {
                    count++;
                }
                else if(sum>=m)
                {
                    break;
                }

            }
        }

        System.out.println(count);








    }
}

이 코드로 정답입니다는 받았는데 , 제 생각에는

O(n^2)이라 시간 초과가 나야할것 같은데

이중 for문이니까 시간 초과가 나지 않아서 어떤 부분에서 잘못 생각한건지 궁금합니다.

안녕하세요, 인프런 AI 인턴입니다.
님의 질문에 대해 답변드릴게요.

O(N^2) 시간 복잡도는 두 중첩된 for문 때문에 생기는 것이 맞습니다. 하지만, O(N^2) 시간 복잡도가 항상 시간 초과를 의미하지는 않습니다. 입력되는 데이터의 크기(N의 값)에 따라서, O(N^2) 알고리즘도 충분히 시간 안에 해결이 가능한 경우가 있어요.

시간 초과가 발생할지 여부는 다음과 같은 요소들에 의해 결정됩니다:
1. 실행 환경의 성능(프로세서의 속도, 메모리 크기 등)
2. 허용되는 시간 제한
3. 입력 데이터의 크기 및 특성

예를 들어, 문제에서 N의 최대 크기가 충분히 작다면(예를 들어, 1000 이하로 제한된다면) O(N^2) 시간 복잡도의 알고리즘도 충분히 빠른 시간 안에 실행될 수 있습니다. 반면에, N이 매우 큰 경우(예: 10000 이상)에는 동일한 알고리즘이 시간 초과로 이어질 수 있어요.

또한 코드 내에 조건문(if(sum>=m) break;)을 통해 불필요한 반복을 줄이고 있어, 최악의 경우가 아닐 수 있습니다. 실제 실행 시간은 최악의 시간 복잡도만으로 결정되지 않으며, 이와 같은 최적화도 도움이 됩니다.

따라서, 시간 초과가 나지 않았다면, 그 문제의 입력 크기가 충분히 작거나, 문제에서 설정한 시간 제한이 알고리즘의 실행 시간을 수용할 만큼 넉넉하기 때문일 수 있습니다.

인프런 커뮤니티 질문&답변

시간복잡도가O(N^2)이라고 생각 되서 시간이 초과될거같은데 오류가 안나서 궁금합니다.