You are viewing a single comment's thread from:

RE: 알고리즘 이야기

in #kr-dev4 years ago

안녕하세요! 제 글에 댓글달아주시는데, 상당히 도움이 많이 되고 있습니다. 지금은 기초를 공부하면서 정리하느라, 시간복잡도까지는 고려를 못하고 있었는데, 좀 더 고려를 해볼 수 있을 것 같습니다! 위에 글을 보니 조금 이해가 되긴 합니다! 그런데 위에서 str.length 부분에서 var slen = str.length해서 for문을 돌리는 것이랑, 그냥 str.length를 쓰는 것이랑 시간복잡도 관련해서 어떤 차이가 있을까요?

Sort:  

for문 안에서 str의 길이가 바뀐다면 str.length로 사용해야겠지만, 그렇지 않다면 var slen = str.length를 사용하는게 일반적으로 조금 더 좋은 선택일겁니다.

str.length의 시간 복잡도는 관련 문서를 봐야 알겠지만, O(1)은 아닐 거라 가정을 하겠습니다.
그러면 시간복잡도가 O(n)인 for문을 하나만 썼더라도, 실제로는 이중 반복문인 것과 같은 시간 복잡도(.length의 시간 복잡도에 따라 O(nlogn),O(n^2) 등)을 갖게 될겁니다.

자바에서의 string length는 int 변수인데 자바스크립트는 다른걸까요? ㅎㅎ

C++ 일부 STL의 크기 판별 함수가 O(n)이더라고요.
JAVA나 javascript는 따로 문서를 봐야 알 수 있을 것 같습니다

C 는 zero terminated string 이라서 len(str) 은 O(n) 입니다.
자바의 경우 String 은 객체로 취급하며 내부적으로 length 를 가지고 있습니다.
참고로 자바 String 은 Constant 이므로 length 가 변하지 않습니다.

Coin Marketplace

STEEM 0.27
TRX 0.08
JST 0.042
BTC 29263.44
ETH 1986.21
USDT 1.00
SBD 2.55