Определите количество всех операций, в синтаксисе которых содержится символ «=», выполняемых в
функции task(), для чего постройте функцию роста f (N)
сложности функции task(), взяв в качестве базовых
(элементарных) операции, в синтаксисе которых
содержится символ «=».
Приведите асимптотическую оценку O(N) исходя из
структуры алгоритма. Является ли она точной?
1. #include "iostream"
2. #include
3. int task(void)
4. {
5. int i, j, k, q, z, m, n, x, s;
6. cin>>n; cin>>x; s=0;
7. for(i=1; i<=n; i++)
8. {
9. for(j=1, z=0; j<=n/2; j+=4)
10. { if (j < 6) for (t=1, s+=2; t 11. z++;
12. if (x > 0)
13. for(k=1; k<=i+1; k=k<<1) s+=k;
14. else
15. for(k=j; k<=2*j; k++)
16. {
17. for (q=k; q<=n; q++) s=s+1;
18. s*=2;
19. }
20. if (z < 10) s+=3;
21. else for (m=i; m<2*j*i; m++) s=x*2+s*i;
22. }
23. }
24. cout< 25. }
26. int main() { task(); }
Объяснение:
Если я правильно понял задачу, нужно посчитать количество операторов, в которых используется знак "=".
Например, на 17 строке:
for (q=k; q<=n; q++) s=s+1;
Здесь считается два знака "=" : один в операторе цикла for (хотя на самом деле в скобках два знака "="), а другой в операторе присваивания s=s+1.
Всего у меня получилось 13 операторов, содержащих знак "=".