• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

15:52 시간복잡도

24.06.12 17:51 작성 24.06.12 18:16 수정 조회수 108

1

강의 문제를 in list로 푸는 경우의 시간복잡도를 O(n^3)라고 하셨습니다.

 

잘 이해가 가지 않아 질문드립니다.

 

  • for loop로 n개의 nums 모든 요소 순회 => O(n)

  • list에 대한 in 연산 수행 => O(n)

    • 최소 한 번은 수행

    • 2번 이상의 경우 while문에서 시간복잡도 계산

  • in 연산 수행의 반복을 while문으로 수행

    • worst case => O(n)

    • [1, 2, 3, 4]의 경우 n-1, n-2, n-3, n-4번 수행

      • 이걸 O(n)으로 취급하는건가요?

 1.

nums의 모든 요소에 대해 항상 while문이 O(n)으로 동작하지 않고 최악의 경우에도 n-1, n-2, n-3, ... 1로 줄어들지 않나요...?

 

아니면,

 2.

for loop로 n번 순회하면서

while loop는 n-1, n-2, n-3번 수행하게되니

두 반복문에 의한 시간복잡도는 등차수열 합의 공식에 근거해 최종적으로 O(n^2)가 되고 이 때 매번 반복하는 in연산도 O(n)이니 최종 시간복잡도는 O(n^3)다. 로 이해하는건가요?

 

  1. 19:47 설명 중

어떻게 while이 모든 경우에 n번 수행될 수 있는건지 궁금합니다...

답변 1

답변을 작성해보세요.

0

안녕하세요. 잇택잇님

 

차근차근 답변을 드리도록 하겠습니다.

 

  1. 말씀하신대로 줄어드는 것이 맞습니다.
    그런데 여기서 잘.. 생각해보면 로직이 등차수열의 행태를 보인다는 것입니다.
    겉에 있는 for loop가 n, while 루프가 n, n-1, n-2의 형태를 등차수열의 합으로 표현하면 이렇습니다.


    n(n-1) / 2 = (n^2 - n) / 2

    정확히 n^2이라고 표현하기에 애매해보이지만, 빅오 표기법에서는 상수 계수는 무시합니다.


    따라서 2n이더라도 표현은 O(n)으로 합니다.
    입력크기가 커질수록 상수계수는 큰 영향을 미치지 않기 때문입니다.



    따라서 이 경우에는 O(n^2)이라고 표현할 수 있습니다.

  2. 2번도 맞습니다.
    list에서 in 연산이 O(n) 위에서 말씀드린대로 반복하는 행위가 O(n^2)
    따라서 O(n^3)로 표현할 수 있습니다.

  3. 모든 경우에 n번씩 수행된다는 의미가 아닙니다. n-1, n-2, n-3...1 이런식으로 줄어들지만, 강의 편의상 그렇게 표현한 것이라고 생각하시면 됩니다. 강의에서도 n번에 가까운 반복이라는 얘기가 나옵니다.


    제가 위에서 설명한대로 등차수열의 합으로 생각하시면 됩니다.

이해가 잘 되었나요?

이해가 잘 안되는 부분이 있거나, 추가적인 질문이 있다면 말씀 주세요!

감사합니다.

잇택잇님의 프로필

잇택잇

질문자

2024.06.12

"n번에 가까운 반복"이라는 설명에 혹시나 했는데 역시나였군요! 등차수열로 접근하는게 맞지만 설명의 편의상 그렇게 설명하셨다고 하니 속이 시원하네요!

 

감사합니다!

 

추가적으로 궁금한 점이 있습니다.

강의에서 나온 연속된 수열의 최대 갯수 구하는 문제 중

 

 

def longestConsecutive2(nums:list[int]) -> int:
  if not nums:
    return 0
  
  # O(nlogn)
  nums.sort()
  ret = 0
  count = 1
  # O(N)
  # []
  for i in range(1, len(nums)):
    if nums[i] == nums[i - 1] + 1:
      count += 1
    elif nums[i] == nums[i - 1]:
      continue
    else:
      ret = max(ret, count)
      count = 1
  return max(ret, count)
    
  
  
def longestConsecutive3(nums:list[int])->int:
  memo = {}
  for num in nums:
    memo[num] = True
  
  # [100, 4, 200, 1, 3, 2]
  ans = 0
  for num in nums:
    prev = num - 1
    if prev not in memo:
      count = 1
      next = num + 1
      while next in memo:
        next += 1
        count += 1
      ans = max(ans, count)
  return ans

 

function2는 O(nlogn)

function3는 O(N)이 맞나요?

 

Leetcode에서 실행하니 2가 더 빠르다고 나와서요...!

문제를 열심히 푸시는 모습이 보기 좋습니다 ㅎㅎ

 

자.. 차근차근 보시죠.

 

첫번째 코드는 O(nlogn)이 맞습니다.

하지만 두번째 코드는 대충 보면 O(n)이라서 더 빠를 거 같지만.. 함정이 있습니다.

 

잘 보면.. for num in nums라고 적혀있습니다.

만약, nums에 중복된 숫자가 있다면 어떻게 될까요?

그리고.. input이 [1,2,3,1,2,3,1,2,3,1,2,3,1,2,3..........] 이런 경우라면요?

num이 1일 때마다.. 조건문도 충족하고.. while문도 충족하지 않을까요?
이러면 바깥은 O(n)이지만 (for num in nums) 내부는.. 어떻게 될지 예상이 되죠?

input값의 형태에 따라서 시간이 크게 달라질 수 있습니다.

 

따라서 루프를 memo의 key값을 기준으로 돌아야 합니다.

왜냐하면.. 키값은 중복이 없으니까요!

 

이 내용을 바탕으로 코드를 바꾸면 첫번째 코드보다 빠른 실행속도를 보실 수 있을 겁니다.

 

감사합니다.

잇택잇님의 프로필

잇택잇

질문자

2024.06.13

와...그런 케이스가 있었겠네요...

 

말씀해주신대로 하니 속도가 많이 개선되었습니다!

hash map(dict) 사용법이 딱히 없어 hash set(set)으로 바꿔보고...in 연산자 대상을 바꿔봤습니다.

LeetCode 기준으로는 O(nlogn) 로직과 거의 비슷하네요...(이럴 수 있나요..?)

 

def longestConsecutive3(nums:list[int])->int:
  memo = set(nums)
  
  # [100, 4, 200, 1, 3, 2]
  ans = 0
  for num in memo:
    prev = num - 1
    if prev not in memo:
      count = 1
      next = num + 1
      while next in memo:
        next += 1
        count += 1
      ans = max(ans, count)
  return ans

이론적으로는 O(N) 알고리즘이 O(N log N) 알고리즘보다 항상 빠르지만, 실제 성능은 다양한 요인에 따라 달라질 수 있습니다.

 

1. 상수 계수:

O(N) 알고리즘에서 상수 계수나 숨겨진 상수가 더 클 수 있습니다.

예를 들어, set 연산에 관련된 오버헤드가 존재할 수 있습니다.
(평균적으로 삽입과 검색은 O(1)이지만, 최악의 경우 O(n)일 수 있습니다.)

2. 데이터 크기:

작은 데이터셋에서는 O(N log N)과 O(N)의 차이가 눈에 띄지 않을 수 있습니다.

데이터셋이 커질수록 이론적인 시간 복잡도의 차이가 더 분명해집니다.

3. 구현의 효율성:

두 알고리즘의 구현 방식에 따라 실제 성능 차이가 날 수 있습니다.

예를 들어, 정렬은 매우 최적화된 라이브러리를 사용할 수 있으므로 실제 실행 시간에 큰 영향을 줄 수 있습니다.
4. 환경적 요인

서버의 성능에 따라서 실행속도가 달라질 수 있습니다. 따라서, 많은 사용자가 서버에 부하를 주면 실행속도도 느려질 수 있습니다.

 

따라서, 이론적인 시간 복잡도는 알고리즘의 성능을 비교하는 데 중요한 지표이지만, 실제 성능은 다양한 요인에 의해 영향을 받을 수 있습니다. 작은 데이터셋이나 최적화된 라이브러리, 서버의 성능 등 여러 가지 요소가 실제 실행 시간에 큰 영향을 줄 수 있습니다.

 

결국, 알고리즘의 실행 속도가 유의미하게 차이나지 않는 이상, 이론적인 시간 복잡도는 하나의 지표일 뿐이며, 실제 환경에서의 성능을 평가할 때는 여러 가지 요인을 함께 고려하는 것이 중요합니다.

 

감사합니다.

채널톡 아이콘