colorxxx   5년 전

어차피 테스트케이스는 많다고 가정해서 걍 돌렸는데 첫번째코드는

가운데원소를 pivot으로 고르고 돌려서 패스가 됐습니다.

두번째코드는 맨 마지막원소를 pivot으로 잡고 돌렸는데

25퍼정도쯤에서 시간초과가 뜹니다.

둘중 하나만 패스되는 경우가 있을수있나요?


시간복잡도의 차이는 크게 없을거라고 생각하는데.. 이런경우는 테스트케이스의 예제형태에 따라 달라진다고 생각하면 되는건가요

아님  제 두번째코드가 잘못된건가요?

jung2381187   5년 전

피벗을 어떻게 잡든 항상 O(N^2) 시간이 걸리는 테스트 케이스를 만들어낼 수 있습니다. 가운데 원소를 피벗으로 잡았을 때 통과된 건 그냥 운이 좋아서입니다.

댓글을 작성하려면 로그인해야 합니다.