알고리즘 문제에서 배열을 static으로 선언하면 공간복잡도는 O(1)인가요?
조회수 580회
예를 들어 문자열을 입력받아 활용하는 알고리즘을 구현하는 경우에 문자열의 최대 1000이라면 전역변수로 미리 1000개의 공간을 char배열로 할당해주고 계속 재사용해준다면 공간복잡도를 O(1)이라고 할 수 있는지 궁금합니다
시간복잡도에 대한 개념적인 설명은 찾기 쉬운데 공간복잡도에 대한 자세한 설명은 찾기가 어려워 혹시 좋은 글이 있다면 알려주시면 감사하겠습니다
1 답변
-
잘은 모르는데 그냥 구글에 대고 space complexity for array라고 쳐보았습니다.
항상 길이가 N인 배열을 (날코딩으로) 만든다면, [공간복잡도는] O(1)입니다. 왜냐하면, 무슨 알고리즘을 어떻게 돌리든, 만드신 배열이 사용하는 공간은 항상 같으니까 말이지요.
만약 그 N값이 입력에 따라서 커질 경우 [공간복잡도는] O(f(n))입니다. 여기서 f(n) 은 입력의 크기 n과 배열의 크기 N에 관한 관계함수고요.
이 번역이 도움이 되면 좋겠네요.
댓글 입력