예를 들어 정렬 알고리즘은 nlogn이 가장 효율적이라고 증명 되어 있지요.
그런데 효율적이라는 개념이 비교 하는 상황 말고도 쓰일 수 있나요?
이산 로그 문제에 대해 공부하다 보니 알고리즘이 여럿 제안되어 있지만
효율적인 알고리즘은 없다. 라는 것을 책에서 읽었는데
결국 효율적으로 계산하려고 개발한 알고리즘일텐데
효율적인 알고리즘이 알려져 있지 않다..라는게 무엇이 기준인지 궁금합니다.
저는 효율적이라는 것이 버블정렬보다 퀵정렬이 효율적이다.
이런 식으로만 쓰이는 줄 알았는데
효율적이라는 것이 하나의 선? 같이 저 글에서는 쓰이는 것같아서
그 의미가 궁금합니다
다항 시간 알고리즘 또는 nlogn 이하
상대적인거 맞을걸?
보통 다항 시간 알고리즘이 없으면 효율적인 알고리즘이 없다고 함
위 말대로 다항 시간 없으면 효율적인게 없음
없다 / 알려진게 없다 / ~는 뭐가 가장 효율적이다
없다: 다항 시간 내 풀 수 없음이 증명됨, 알려진게 없다: 다항시간안에 되는지 부정도(불가능하다는 증명) 긍정도(실례;알고리즘) 못함, ~는 뭐가 가장 효율적이다: 하계이론이라고 부르는데 딱 정해진 효율성의 하한이 있다는거, 이게 다항시간 넘으면 없는거.
다항시간 넘는, 즉 효율적인 알고리즘이 없으면 휴리스틱 등으로 최적화를 시키는 루트를 탐.