해결된 질문
24.06.12 17:51 작성
·
163
·
수정됨
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)다. 로 이해하는건가요?
19:47 설명 중
어떻게 while이 모든 경우에 n번 수행될 수 있는건지 궁금합니다...
답변 1
0
2024. 06. 12. 22:21
안녕하세요. 잇택잇님
차근차근 답변을 드리도록 하겠습니다.
말씀하신대로 줄어드는 것이 맞습니다.
그런데 여기서 잘.. 생각해보면 로직이 등차수열의 행태를 보인다는 것입니다.
겉에 있는 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번도 맞습니다.
list에서 in 연산이 O(n) 위에서 말씀드린대로 반복하는 행위가 O(n^2)
따라서 O(n^3)로 표현할 수 있습니다.
모든 경우에 n번씩 수행된다는 의미가 아닙니다. n-1, n-2, n-3...1 이런식으로 줄어들지만, 강의 편의상 그렇게 표현한 것이라고 생각하시면 됩니다. 강의에서도 n번에 가까운 반복이라는 얘기가 나옵니다.
제가 위에서 설명한대로 등차수열의 합으로 생각하시면 됩니다.
이해가 잘 되었나요?
이해가 잘 안되는 부분이 있거나, 추가적인 질문이 있다면 말씀 주세요!
감사합니다.
2024. 06. 12. 23:51
문제를 열심히 푸시는 모습이 보기 좋습니다 ㅎㅎ
자.. 차근차근 보시죠.
첫번째 코드는 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. 00:01
와...그런 케이스가 있었겠네요...
말씀해주신대로 하니 속도가 많이 개선되었습니다!
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
2024. 06. 13. 00:38
이론적으로는 O(N) 알고리즘이 O(N log N) 알고리즘보다 항상 빠르지만, 실제 성능은 다양한 요인에 따라 달라질 수 있습니다.
1. 상수 계수:
• O(N) 알고리즘에서 상수 계수나 숨겨진 상수가 더 클 수 있습니다.
• 예를 들어, set 연산에 관련된 오버헤드가 존재할 수 있습니다.
(평균적으로 삽입과 검색은 O(1)이지만, 최악의 경우 O(n)일 수 있습니다.)
2. 데이터 크기:
• 작은 데이터셋에서는 O(N log N)과 O(N)의 차이가 눈에 띄지 않을 수 있습니다.
• 데이터셋이 커질수록 이론적인 시간 복잡도의 차이가 더 분명해집니다.
3. 구현의 효율성:
• 두 알고리즘의 구현 방식에 따라 실제 성능 차이가 날 수 있습니다.
• 예를 들어, 정렬은 매우 최적화된 라이브러리를 사용할 수 있으므로 실제 실행 시간에 큰 영향을 줄 수 있습니다.
4. 환경적 요인
서버의 성능에 따라서 실행속도가 달라질 수 있습니다. 따라서, 많은 사용자가 서버에 부하를 주면 실행속도도 느려질 수 있습니다.
따라서, 이론적인 시간 복잡도는 알고리즘의 성능을 비교하는 데 중요한 지표이지만, 실제 성능은 다양한 요인에 의해 영향을 받을 수 있습니다. 작은 데이터셋이나 최적화된 라이브러리, 서버의 성능 등 여러 가지 요소가 실제 실행 시간에 큰 영향을 줄 수 있습니다.
결국, 알고리즘의 실행 속도가 유의미하게 차이나지 않는 이상, 이론적인 시간 복잡도는 하나의 지표일 뿐이며, 실제 환경에서의 성능을 평가할 때는 여러 가지 요인을 함께 고려하는 것이 중요합니다.
감사합니다.
2024. 06. 12. 23:09
"n번에 가까운 반복"이라는 설명에 혹시나 했는데 역시나였군요! 등차수열로 접근하는게 맞지만 설명의 편의상 그렇게 설명하셨다고 하니 속이 시원하네요!
감사합니다!
추가적으로 궁금한 점이 있습니다.
강의에서 나온 연속된 수열의 최대 갯수 구하는 문제 중
function2는 O(nlogn)
function3는 O(N)이 맞나요?
Leetcode에서 실행하니 2가 더 빠르다고 나와서요...!