인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

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

australialove19님의 프로필 이미지
australialove19

작성한 질문수

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

2. 공통원소구하기(Two Pointers Algorithm)

시간 복잡도 개념

작성

·

173

0

안녕하세요 !

커뮤니티에 게시글을 보다가

'' 이 문제의 해법은 sort를 피하겠다는 것이 아니라 2중 for문 즉 시간복잡도 O(n^2)를 피하겠다는 뜻입니다.

참고로 sort의 시간복잡도는 O(nlogn)입니다. 

 '' 이런 답변을 봤어요~

구글에 시간복잡도에 대해서 검색해봐도 다 이런 수학 기호들이 난무하는데요..!

어떻게 쉽게 이해하면 좋을까요..?

저는

function solution(arr1, arr2) {
    let answer = [];
    for(let x of arr1) {
        for(let i = 0; i < arr2.length; i++) {
            if(x === arr2[i]) answer.push(x);
        }
    }
    answer.sort((a, b) => a - b);
    return answer;

이렇게 풀었는데 투 포인터로 푸는 방식보다 많이 느린가요??

더 빠르다, 느리다의 기준을 모르겠습니다 ㅠㅠ

답변 1

1

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

for문이 반복하는 횟수가 많으면 더 느리다고 판단하시면 됩니다. 이제 입문단계라 이런 부분이 잘 와닿지 않을 수 있습니다. 너무 연연하지 마시고 문제풀이에 집중하세요. 문제를 풀다보면 느낌이 올겁니다.

australialove19님의 프로필 이미지
australialove19

작성한 질문수

질문하기