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

"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값을 기준으로 돌아야 합니다.

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

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

감사합니다.

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

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

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. 환경적 요인

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

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

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

감사합니다.