시간 복잡도는 어떻게 다릅니 까?

Question

값을 저장 한 다음 사용하면 시간이 절약됩니까?
예 :

while(i<strlen(s)) 
//code 

및

int n = strlen(s); 
while(i<n) 
//code 

함수의 리턴 값이 먼저 저장된으로서 제 2 방법에 대한 시간 복잡도 낮은하고, 따라서 기능은 루프에 진입 할 때마다 호출 회피 사용?

Answer 1

, i가 (아마 0에) 적절하게 초기화 및 루프 본문에 증가 가정을, 당신은 문자열 s 주변마다의 문자 수를 계산합니다 루프에 N 문자가있는 경우 N 비교를 수행합니다 (은 문자열의 각 문자를 '\0'과 비교하므로 명시적인 루프를 N 번 수행하고 strlen() 내부의 루프를 수행하므로) 각 호출을 N 번) O (N)의 코드를 만듭니다.

두 번째 예에서는 다시 i이 초기화되고 루프 본문에서 증가되면 문자의 수를 한 번 계산하므로 N 개의 비교를 수행하여 코드 O (N)을 만듭니다.

옵티마이 저가 strlen()에 대한 호출을 루프 제어에서 안전하게 최적화 할 수 있는지 여부는 루프 본문의 내용에 따라 다릅니다.컴파일러가 모든 것을 볼 수 있거나 호출 된 코드가 문자열 s을 합법적으로 수정할 수 없다는 것을 결정할 수 있다면 루프 제어에서 strlen()으로 호출을 이동시켜 효과적으로 두 번째 루프의 O (N) 성능을 제공 할 수 있습니다 . 루프의 본문이 함수를 호출하고 s에 대한 비 const 포인터를 함수에 전달하면 컴파일러는 문자열이 수정되지 않았다고 가정 할 수 없으며 각 반복마다 strlen()을 호출해야 할 수 있습니다.

Answer 2

영리한 컴파일러가 두 번째 작업을 수행합니다. 그러니 걱정하지 마시고 은 희박하지 마십시오 조기 최적화!

---

길이가 고정 값이고 루프 당 함수 호출을 피하기 때문에 두 번째 코드를 원합니다.

---

하지만 컴파일러는 그렇게 할만큼 영리합니까? 너가 그에게 역시 말하면! 아래의 예를 참조하십시오 :

첫째, 나는 최적화없이 플래그 를 컴파일하고 있습니다 :

C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall nostore.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
That took 27.701602000 seconds wall clock time. 
C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall store.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
That took 12.100676000 seconds wall clock time. 

을하지만 우리는 최적화 플래그를 사용하면 어떻게됩니까?

C02QT2UBFVH6-lm:~ gsamaras$ gcc -O3 -Wall nostore.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
That took 0.004949000 seconds wall clock time. 
C02QT2UBFVH6-lm:~ gsamaras$ gcc -O3 -Wall store.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
That took 0.005283000 seconds wall clock time. 

컴파일러가 저보다 낫습니다! 컴파일러는 오늘날 사람들이 실수로 생각하는 것처럼 바보가 아닙니다.

타이밍을 위해 나는 Time measurements에서 Nomimal Animal의 접근법을 사용했습니다.

char* str = "What's faster? What's a premature optimization? Am I a vi$ 
int i = INT_MAX; 

// int n = strlen(str); 
// while(n); 
while(strlen(str)) { 
    // do some random work so that you don't get 0 timing 
    int a = 3; 
    double pi = 3.14; 
    a /= pi; 
    a = a % (i + 1); 
    // break when 'i' is 0 
    if(!i) 
     break; 
    --i; 
} 

---

되지만 최적화 플래그 벤치마킹 중요한 그 다음은

내가 실행 대구입니까? YES,이 질문을 확인 : 첫 번째 예에서 Poor performance of stl list on vs2015 while deleting nodes which contain iterator to self's position in list