14888번 - 연산자 끼워넣기
문제를 풀다가 시간 복잡도를 정확히 구했는지 알고싶어서 질문드립니다.
recursive 함수 호출(oper.size()를 n이라고 할때)
1회 호출시 n-1번 호출되고
2회 호출시 (n-1)*(n-2)
...
n회 호출시 (n-1)*(n-2)...1
=====> n!의 증가율을 보이고
1번 호출될때마다 n!의 증가율을 보이므로
최대 n번이므로 n*n!
시간 복잡도는 대략 O(n!*n) 계산되는데 이 계산법이 맞나요?
댓글을 작성하려면 로그인해야 합니다.
ghwjdgks 5년 전
문제를 풀다가 시간 복잡도를 정확히 구했는지 알고싶어서 질문드립니다.
recursive 함수 호출(oper.size()를 n이라고 할때)
1회 호출시 n-1번 호출되고
2회 호출시 (n-1)*(n-2)
...
n회 호출시 (n-1)*(n-2)...1
=====> n!의 증가율을 보이고
1번 호출될때마다 n!의 증가율을 보이므로
최대 n번이므로 n*n!
시간 복잡도는 대략 O(n!*n) 계산되는데 이 계산법이 맞나요?