[자료구조] Program step 정의, 방법

2️⃣ Program step

• 정의
  - 프로그램의 segment를 세는 방법을 의미
  - 프로그램이 어떤 수행을 하던지, 그 라인을 몇 번 수행하는지를 측정하고자 하는 것
  - running time이 인스턴스 특성과 무관한 특징을 가짐
  - 함수 call (recursive call 포함) 등으로 발생하는 시스템 스택 내의 activation record의 동적 증감
  
  
• 방법

    float sum(float list [], int n){
    	int count = 0;
    
    	float tempsum = 0;         // sum 함수의 시작 +
    	count++;
    
    	int i;                     //선언은 step으로 X
    	for(i=0; i<n; i++){ 
    		count++;                 //for문이 몇 번 도는지 +n
        
    		tempsum += list[i];
    		count++;                 //더하기 연산을 했으니 +n
    	}
    	count++;                   // for문이 끝났다는 것을 알려주는 +1
    	count++;                   // return하기 위한 +1
    	return tempsum;
    }

- Total Count = 2n +3

• 목적
  - 두 프로그램들의 시간복잡도를 상대적으로 분석 및 비교
  - 인스턴스 특성이 변함에 따라 run time의 실제 수행 라인 수가 얼마나 변하는지 예측
  
  

• 문제

  • 정확한 step 시간 측정이 어려우며 step의 개념 자체가 부정확하기 때문에 비교하는데 어려움
  • Program step 방법의 목적에 유용하지 않음

*참고

#6 [C 자료구조] 알고리즘 성능의 척도: 시간 복잡도의 계산법