[질문] 파이썬 시간복잡도에 대해서

[익명(112.171)]

계산시간 10초 제한일때, N이 주어질 때 어느정도까지 O(N)으로 풀 수 있음? 좀 더럽게 N이 아니라 일반적인 케이스임.

대충 O(N)인 dp문제라고 생각해도 될듯.

난 대략 10초에 10만이면 O(N)인가? 하고 생각하는데 맞는지는 모르겠음.

[익명(183.100)]

보통 1초에 2천만번 이라고 생각하는거 같음 10초니까 n이 2억까지

[익명(112.171)]

오 ㄳㄳ

[캐티(tae826)]

근데 시간복잡도랑은 별개로 입력시간도 영향을 되게 많이 받긴 함. N이 1000만이면 C에서 O(N)은 1초에 당연히 돌아가지만 1000만개 입력이 1초안에 안 되는 것처럼

[익명(211.197)]

ㅇㅈ 출력도

[익명(121.180)]

mmap이나 fread쓰면 돌아갈듯?