함수의 시간복잡도는

Question

function markStart(n: number) {let star &#61; &#34;*&#34;;for(let i &#61; 0; i <&#61; n; i &#61; i&#43;1 ) {console.log(star)star &#61; star &#43; &#34;*&#34;}} 위의 함수의 시간복잡도는 O(n) 인가요? gpt가 등차수열 합만큼 계산한고 O(n^2) 라고 뻘 소리를 해서 와 내가 뭔가 잘못 알고 있는게 있나 싶어서 문의 글 남깁니다.

Throwaway · Answer

예 O(n) 입니다

カワウソ · Answer

반복문의 횟수가 시간 복잡도는 아님을 생각해야할 것 같습니다. 대부분의 언어에서 문자열 결합은 연산이 많다고 하네요.

BGProgramming · Answer

console.log()를 보니 타입스크립트를 사용한 것 같네요.그렀다면 언어는 자바스크립트겠구요.자바스크립트의 문자열은 상수로 취급됩니다.그렇기에 star = star + "*" 은 기존 문자열을 새로 문자를 덧붙여서 새로운 메모리 공간에 배정되겠군요.그런데 문자열에 새 문자를 덧붙이기 위해서는 어떻게 해야 되요?문자의 마지막까지 가서야 문자를 덧붙일 수 있습니다.그렇기에 star = star + "*" 구문에서 n의 루프가 추가되는겁니다.흔히 하는 실수가 자신의 함수에서만 시간값을 계산하고 여기서 호출하는 함수나 로직이 걸리는 시간을 계산을 놓치는 경우가 있습니다.위의 로직을 더 엄격히 말하면 실제는 자바스크립트의 문자열 처리 방식이 파스칼 방식으로 처리하는지 nul로 끝나는 문자열로 처리하는지는 정의되지 않았습니다. 이에 더 엄밀히 말하면 따져야할게 있습니다만...GPT의 답변이 엉뚱한 내용같지는 않습니다.

개발잡부 · Answer

GPT

함수의 시간복잡도는

4개의 답변

Q&A 목록