시간복잡도 공부하는데

[익명(183.99)]

왜 내가 짠 코드는 O(n)이 O(nlogn) 보다 느리냐;; 

개짜증나네 진짜

- dc official App

[리슬링?(lucid74)]

니가 짠 코드가 O(N)이 아닌가보지

[익명(183.99)]

for 문 하나쓰면 O(n) 맞지않나? - dc App

[리슬링?(lucid74)]

루프 안에 들어간 코드가 상수시간에 작동해야 O(N)

[익명(183.99)]

A = [1, 2, 3] B = [] for i in A: if i not in B: B.append(i) 이렇게 짜면 O(n) 맞지않아? - dc App

[리슬링?(lucid74)]

입력값을 최대로 해보고 남의 코드랑 테스트해봐 입력값 커질수록 차이가 많이 날거임

[익명(183.99)]

여기서 A의 값을 n으로 두고 입력받은 다음에 nlogn인 a.sort랑 비교해보고 있거든... 근데 어떤 값을 넣던지간에 a.sort가 빠르게 나와서 이상하다 진짜 ㅜㅠ 뭐가 문제인지 모르겠어 - dc App

[리슬링?(lucid74)]

A의 원소의 개수를 1e7개정도? 큰 값으로 넣고 테스트해봐

[익명(183.99)]

그렇게하면 컴퓨터 성능이 딸려서 출력이 안되지 않나? 한 10-20분 기다려가면서 해봐도 댐? - dc App

[리슬링?(lucid74)]

O(N)은 1~2초면 될텐데

[익명(183.99)]

한참 더 나온다.... 내가 코드를 잘못짠건가 ㅠㅜ 위에 내가 적은 코드 O(n) 맞기는 한 거지? - dc App

[익명(183.99)]

계산이 안되고있어 - dc App

[리슬링?(lucid74)]

아 씨발 파이썬 별로 안해서 제대로 안봤는데 if i not in B 이거때문에 그런듯 ㅇㅇㅇ

[익명(183.99)]

ㅇㅎ;;; 다른걸로 바꿔야하나;; 빡머가리라서 저거 만들려면 not in 말고 생각 안나는데.... 저거때문은 맞는거같다 햐... - dc App

[익명(183.99)]

생각해보니까 not in 쓰면 당연히 n2겠네ㅋㅋㅋㅋㅋ 고맙다 - dc App

[익명(106.101)]

in이 O(N)이고 .append도 느려서 그런듯