알고리즘의 유형

읽어보기 전에...:컴퓨터는 엄청 큰 계산기 랍니다. 그말은 수학을 조금은 알아야 한다는것이지요 하하하

읽어보시기 전에 로그,제곱,등은 알아두고 읽어보시는것이 이해가 더 잘될것 같습니다

1.

입력 자료수에 관계없이 일정한 시간을 갖는 알고리즘이다. 프로그램에서 대부분의 명령으로 한번이나 몇번만 실행된다. 전체적 프로그램이 이런경우라면 실행시간은 상수(1처럼)가 된다. 알고리즘을 설계하거나 테스트시 도전해볼만 하다.

log N.

입력자료 N에 따라라 실행시간이 Log N을 만족한다면 N이 증가함에 따라 실행시간이 조금씩 늘어난다. 커다란 문제를 해결할때 조금씩 잘게 쪼갤때 나타나는 알고리즘이다.로그 가 그렇듯이 base에 따라 결과가 달라지지만 그렇게 크게 다르지는 않다. 예를들어 N이 1000일때 밑이 10이라면 결과는 3이 나오지만 밑이 2라면 약 10이다 이차이는 매우 미미하다. 이 유형의 알고리즘은 매우 바람직한 실행시간을 가지는데 성능의 좋은 알고리즘은 대부분 Log N의 수행시간을 가진다.

N log N.

커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 알고리즘이다 N이 두배가 많아지면 실행시간은 두배보다 조금 더 많이 늘어난다.

N^2.

이 유형은 이중 루프 내에서 입력자료를 처리하는 경우에 나타난다. N값이 큰값이 되면 실행시간은 감당하지 못할정도 커진다 그러므로 많은 양의 입력자료에 대해서는 사용이 부적절 하다. N이 두배로 늘어나면 실행시간은 4배로 늘어난다.

N^3.

이 유형은 앞의 유형과 비슷하게 입력자료를 삼중 루프내에서 처리하는 경우에 나타난다 N값이 커짐에 따라 실행시간은 훨씬더 커지게 된다. 앞의 유형과 마찬가지로 많은 입력자료에 대해서는 부적절하며 문제가 있는 알고리즘이다 N이 두배가 늘어나면 실행시간은 8배로 늘어난다.

2^N

입력자료가 늘어남에 따라 급격하게 실행시간이 늘어난다. 흔하지는 않지만 알고리즘을 개발할떄 보인다. 하지만 개발되고 난후로 더좋은 알고리즘으로 개선된다. N이 두배로 늘어나면 실행시간은 제곱이 된다.

실행시간이 오래걸리는것 순서대로 알고리즘을 적어 보았는데요 가장 효율적인 유형은 logN과 NlogN 인것같습니다!