알고리즘 성능평가
알고리즘 성능을 계산할 때는 절대시간과 상대시간이 나오는데
상대시간에서 연산(if연산으로 가정했음)의 횟수를 계산한다.
연산횟수를 계산을 할 때는
최선의 경우 (best case)
평균의 경우 (average case) —- quick sort만 쓴다.
최악의 경우 (worst case)
- 이 알고리즘은 최악의 경우에도 big o(n)가 이것임을 보장한다.
그럼 big o는 무엇일까?
n –> T(n) = 3n ** 2 + 2n - 1 –> 그림을 결정하는데 차수가 가장 좋은 것이다.
여기서 3도 버리고 n ** 2 을 O(n ** 2)이렇게 적는다. 이거를 Big O of 엔 제곱이다 라고 말하거나 order of 엔 제곱 으로 표현하기도 한다.
O(n ** 2) 이것만 보고도 성능을 파악할 수 있다.
O(n) —> upper bound —–> 최악의 경우에도 이것보다 나빠지지 않는다.
W(n) —> under bound —–> 최선의 경우에도 이거보다 나아질 수 없다. (쓰지 않음)
세타(n) —> 위에 2개를 더한것 —–> 최선의 경우에도 이거보다 나아질 수 없고 최악에도 이것보다 나빠지진 않는다. 제일 좋은 것인데 구하기가 어렵다.
T(n)의 트랜드가 중요하다. 즉 데이터의 갯수가 늘어날때 점점 성능이 좋아지는지
아니면 성능이 나빠지는지가 중요하다
가장 좋은 성능
- O(1) : 상수시간(constant) 데이터의 갯수가 4개에서 100만개로 늘어나도 연산횟수는 늘어나지 않는다.
- array의 indexing arr[3] # 꼭 1일 필요는 없다.
- linked list 의 insert(), delete()
O(log n) : 로그시간 데이터 갯수가 늘어나도 연산횟수는 log 그래프로 증가
binary search
BST insert(), search(), delete()
O(n) : 선형시간
linear search
array의 insert , delete
linked list의 search()
O(n*log n)—> 일반 n그래프에 log n을 꼽해서 조금 더 높아지는 그래프
quick sort
merse sort
hoop sort
comparison sorting은 그 알고리즘 속도가 nlogn보다 더 좋아질 수 없다.
O(n ** 2) —> 미친듯이 가팔라진다.
bubble sort
msert sort
5번과 4번을 비교하면 4번이 훨씬 훨씬 좋다.!
예를 들어보면)
Time complexity
O(n)을 보장한다 해서 막 썼는데 서버가 터짐
ram에서 cpu로 갈때는 20cycle
하드 디스크 500000cycle이다.
만약에 n이 하드디스크에 있는 것이라고 하면 미친듯이 느린 것이다.
그럼 그것을 제공하는 곳에 전화해서 하드에서 가져오는지 파악
실제 현업에서 나가서 뻗는다 이러면 벤치마킹을 해보고 판단해야 한다.
if for문을 3개 쓰는 알고리즘이 있으면 쓰면 안된다. 우리가 알고리즘 짜는데 만약에 for문이 3개 나온다하면 그냥 다시 짜면 된다.
double에서는
mantisadigit - 53
1111 1111 1111 1111—-> 53개까지 했을 때 어디까지 커버가 가능할까?
9,007,199,254,740,991 —> 총 15자리까지 완벽 커버가능하다.
여기서 제일 마지막 1은 더 이상 커져도 신뢰할 수 없다.
결론 도출
- 나는 데이터를 삽입하는 경우보다 서칭만 한다 —> 꼭 배열을 쓴다.
- 나는 데이터를 찾는 경우는 잘 없지만 삽입 및 딜리트를 한다 –> linked
- 나는 다 적당히 한다. —> BST
성능 평가에 대해 조금 더 공부해보려고 한다.
What does T(n) mean in relation to O(n)?
When discussing an algorithm, the common usage of the symbol 𝑇T is to represent its time complexity. 𝑇T is a function. The input to this function is the input size, the output is the (worst-case) running time for an input of that size. Therefore, 𝑇(𝑛)T(n) is a number: the number returned by the function 𝑇T when given the number 𝑛n. This number is the running time of our algorithm on an input of size 𝑛n. The 𝑂O in “𝑂(𝑛)O(n)” is not a function. This is Big O notation. In particular, the symbol 𝑂(𝑛)O(n) represents the class of all functions that grow (asymptotically) at most as quickly as the linear function 𝑓(𝑛)=𝑛f(n)=n. Big O notation gives us a convenient way to talk about upper bounds. For example, we can say “the time complexity of this algorithm is 𝑂(𝑛2)O(n2)” (formally: “𝑇∈𝑂(𝑛2)T∈O(n2)”) to say that the running time of the algorithm is at most quadratic in the input size. Sometimes, you can see both symbols being used in a single equation. For example, the time complexity of MergeSort is commonly described by the following recurrence: “𝑇(𝑛)=2𝑇(𝑛/2)+𝑂(𝑛)T(n)=2T(n/2)+O(n)”. The meaning of the above statement: For any 𝑛n, the time 𝑇(𝑛)T(n) needed to sort 𝑛n elements can be computed by taking the time 𝑇(𝑛/2)T(n/2) needed to sort 𝑛/2n/2 elements, multiplying that time by 2, and adding something extra. That something extra must be at most linear in 𝑛n.
What does T(n) mean in relation to O(n)? - Quora
해석 :
알고리즘을 논할 때, 기호 T의 일반적인 용도는 시간 복잡성을 나타내는 것이다.
T는 함수다. 이 함수에 대한 입력은 입력 크기, 출력은 해당 크기의 입력에 대한 (최악의) 실행 시간이다.
따라서, T(n)는 숫자다: n을 부여했을 때 T 함수가 반환하는 숫자다. 이 숫자는 크기 n의 입력에 대한 우리의 알고리즘의 실행시간이다.
“O(n)”의 O는 기능이 아니다. 이것은 Big O 표기법이다. 특히 기호 O(n)는 선형 함수 f(n)=n만큼 빠르게(증식적으로) 성장하는 모든 기능의 클래스를 나타낸다.
Big O 표기법은 우리에게 상위에 대해 이야기할 수 있는 편리한 방법을 제공한다. 예를 들어, 우리는 “이 알고리즘의 시간 복잡성은 O(n2)”(공식적으로 “TOO(n2))라고 말할 수 있다.
때때로, 당신은 하나의 방정식에 두 개의 기호가 사용되는 것을 볼 수 있다. 예를 들어, MergeSort의 시간 복잡성은 일반적으로 “T(n)=2T(n/2)+O(n)”에 의해 설명된다.
상기 문장의 의미 : 어떤 n에 대해서도 n 요소를 분류하는데 필요한 T(n/2)는 n/2 요소를 분류하는 데 필요한 시간을 취하고 그 시간을 2로 곱한 후, 어떤 것을 추가함으로써 계산할 수 있다. 그 어떤 특별한 것은 n에 가장 직선적일 것이다.
—-» T 함수는 함수에 대한 최악의 실행시간이다. T(n)은 숫자인데 n 크기에 대한 자료를 함수에 넣었을 때 걸리는 실행시간이다.
—-» 우리가 말하는 알고리즘의 성능이 어떤 것인지 T of N 을 항상 구할 수는 없으므로 big O를 구하는 것을 배운다.