시간 복잡도만으로는 그 복잡도에서 1이 의미하는 게 얼마나 무거운 연산을 의미하는지 알 수 없기 때문에 정확히 얼마가 걸릴 것이라고 예측하는 건 거의 불가능합니다. 똑같은 로직이 똑같은 시간 복잡도를 가진다고 하더라도 실제로 코드를 어떻게 작성했는지에 따라 몇 배 이상 차이가 날 수도 있습니다.
지금은 대략적으로만 생각하시는 것이 좋습니다. 쉬운 문제들의 경우 시간을 대체로 매우 여유 있게 주는 편이기 때문에, 적어도 의도된 풀이는 시간 복잡도로 계산한 값이 초당 1억 이하일 거라고 생각하시면 됩니다. 그 값이 1억이 안 되는데도 1초 안에 못 돌 정도로 비효율적인 건 거의 없습니다.
ktj7916 4년 전
알고리즘 초보자입니다 ㅎ;
제가 이 문제를 처음에 시간초과가 걸릴거같긴했는데 완전탐색으로 접근하였습니다.
결과는 당연히 시간초과였지만 ㅎㅎ
멱집합식으로 체크해서 시간복잡도가 O(2^n)인것도 알고있습니다.
제가 궁금한점은 이 시간복잡도를 어떻게 사용하는가입니다.
최대 입력이 100으로 주어지니 시간이 O(2^100)인건 알겠으나 이 숫자가 엄청나게 크다는것과 비효율적이라는것을알뿐
어디에 적용하는지 모르겠습니다.
그렇다보니 처음 문제에서 시간제한을 주어도 그게어느정도인지 가늠이안갑니다.
시간복잡도에따른 시간계산에대해서 알려주실 고수분있으신가요 ㅠㅠ