[알고리즘]시간복잡도(Time Complexity), 순차탐색 알고리즘 수행시간 계산법

안녕하세요 붐붐몬입니다. 
남친몬이 글좀 올리라고 타박줘서 고민하다 보니 효율성표현! 까지만 하고 ㅋㅋㅋㅋㅋ
계산법을 손으로만 적은걸올려둬서 뭐 이건 뭐하란거지 라는 느낌이겠더라구요 그래서 ㅋㅋㅋ 
오늘은 수행시간 계산법에 대해서 (이론적으로) 알려드립니다. 
부산여자라서 말이 좀딱딱해요 그래도 이해좀
알고리즘 효율성 및 시간복잡도를 나타내는 종류 같은 것은 이전 글에 있어요. 
레포트 용은 저거 보시면 됩니다...총총총

 

https://boomboommon.tistory.com/27

[알고리즘] 알고리즘 효율성표현(ALGORITHM)(4)

이제는 수행시간을 계산해보겠습니다.

1. 수행시간 가정
 + 한 문장 씩 순차적으로 진행될 것
 + 하나의 연산을 하나의 문장(명령문)으로 표현
 + 기본 연산의 수행횟수를 카운팅

2. 수행시간 = sum(각 명령문의 수행되는 횟수 x 각 명령문의 수행시간)
(이론적으로는 이런데 문제가 있어요! 그건 3. 참고)

 수행시간 = sum(각 명령문의 수행되는 횟수 x 각 명령문의 수행시간)

 

3. 수행시간 계산시 문제점
- 잘생각해봐요 무슨 코드가 for 블라블라 끝 도 아니고 for안에 for가 들어가고 그안에 if나 else가 들어 갈건데 
c++하면 클라스가 남다르지 그러면 입력의 크기가 커질거고 그러면 수행시간이 증가 하겠죠?

엄청많은 이유가 있지만 세가지로 정리하면 

① 입력상태에 따라 수행속도가 달라짐 
▶▶▶▶ 해결: 우선 입력의 크기 함수로 표현함

입력의 크기가 n일 때 알고리즘의 최악의 시간은 T(n) 함수로 주어짐
T(n) = 0.1n²+n+100

② 입력 상태에 따라 수행속도가 달라짐
▶▶▶▶ 해결 : 다양한 입력에 따라 각 경우의 수행시간 계산 후 이들의 평균 또는 가중 평균을 택함 

AverageTime(n) = Sum(P(i) *t(i)), i∈S_n
P(i) : 입력 i가 발생할 확률
t(i) : 입력 i일 때 알고리즘 수행시간
S_n   :총 개수 n인 입력들의 집합 (0≤i ≤n)

③ 평균 수행시간은 평균 수행시간은 특정 입력에 대한 수행시간을 의미하지도 않고 계산도 쉽지 않음
▶▶▶▶해결 : 일반적으로 수행시간의 상한을 의미하는 최악 수행시간(BIG-0) 사용

그래서 보통

수행시간, 평균시간, 최악시간을 계산합니다. 

최선은 보통 하지않아요(최선을 할정도면 manager 급인데 manager급은 제글을 읽지않아요 이미 알고있죠)

++++++시간의 복잡도 
      (1) 최악 경우 분석(worst case analysis) - Big-Oh  
          -  어떤 입력이 주어지더라도 얼마 이상을 넘지 않는다’  
          단위연산이 수행되는 횟수가 최대인 경우  
          최악 경우 시간(Worst-Case-Time)  
          : 입력 크기가 n인 모든 입력에 대해 알고리즘을 실행하는데 걸리는 최대 시간  

      (2) 평균 경우 분석(average case analysis)  
          -  입력이 무작위로 주어진다고 가정  
          모든 입력에 대하여 단위연산이 수행되는 기대치(평균)을 선택  
          평균 경우 시간(Average-Case-Time)  
          :입력 크기가 n인 모든 입력에 대해 알고리즘을 실행하는 데 걸리는 평균 시간   

      (3) 최선 경우 분석(best case analysis) – BIG-omega  
          -  단위연산이 수행되는 횟수가 최소인 경우 선택  
          최적의 알고리즘 고안하는데 참고자료로 사용  
          최선 경우 시간(Best-Case-Time)  
          :입력 크기가 n인 모든 입력에 대해 알고리즘을 실행하는 데 걸리는 최소 시간 

---

4. 수행시간 계산 예시

분명 과제로 순차 탐색 나올거니깐 순차 탐색을 예시들어줄게영 ㅇㅅㅇ+

순차 탐색 알고리즘 : n개의 데이터가 있는 리스트 A 값에서 x 값이 존재하는지 찾는 알고리즘

코드는  이거 

SeqSearch(n,A,x)
v=1;
while(v<=n && A[v]!=x)
v=v+1;
return v;

입력 : n, A,x
출력 : v(return 값)

그러면 시간을 어떻게 계산을 하느냐?

순차 탐색 코드 수행시간 확인방법

---

수행시간 : 

T(n) = (1*C1) + {k(C2+C3+C4)} + {(k-1)*C5} + (1*C6)
          = {k(C2+C3+C4)} + {(k-1)*C5}  + (C1+C6)
          =xk +y(k-1)+z

---

평균시간 :

---

최악시간:
 (입력이 발생할 확률이 p가 0인 상황)

  WT(n) = (x+y)n+(x+z)

 

아 손으로계산하는 편이라서 스캔해서 올립니다... 

 

평균시간
-확률이 p인 알고리즘의 수행시간
-X의 값이 A안에 없을 경우(n+1 일 때) 
(1-p)(x(n+1)+ny+z) 까지 더한 뒤 평균 시간 측정

최악시간
-이 알고리즘에서는 n+1까지 갔을 경우 가장 오랜 시간이 소요됨
-그러므로 P가 0일때 가장 최악의 시간이 나옴

 

우선 이렇게 올리고 복잡도의 점근적표현은 다음글에.,....남친몬이 타박하면 올릴게요....

어짜피 코나만 보잖아 흑흑흑흑

알고리즘 처음하면 뇌자알도 책좋아요