Как рассчитать временную сложность этой функции?

Question

Привет всем Я пытался вычислить время сложности этой функции, но я не могу понять, как вычислить сложность этого «для цикла»

01 int* f(int a[], int n) { 
02 int i = 1; 
03 int *s; 
04 s = calloc(n, sizeof(int)); 
05 while (i < n) { 
06  for (j=0; j < i; j++) 
07   s[i] = s[i] + a[j]; 
08  i = i*2; 
09 } 
10 return s; 
11 } 

упражнения просит временную сложность по отношению к измерение «п» из массива

Я не думаю, что линии 02,03,04 являются большой проблемой, потому что они должны иметь O (1) сложность

для цикла в то время как, если я оставить в стороне " для цикла "на мгновение, так как« i »умножается на два каждый раз, когда временная сложность должна быть 2^k<n --> k= log_2(n)

Но как насчет цикла for? он должен выполняться «i» раз, но как я могу выразить это по отношению к «n»?

P.S: как я пишу математические символы, я не могу найти что-либо в редакторе

Answer 1

Внешний цикл выполняется log(n) раз, с i принимает значения 1, 2, 4, 8, ... < п, где п < самый большой степенью 2 меньше п.

Для каждого значения i внутренний цикл выполняется i раз.

Итак, у вас есть 1 + 2 + 4 + 8 ... + < n. Эта сумма меньше 2 * n. Таким образом, ответ O (n).

Некоторые другие люди считали, что это O (n * log (n)), но ошибка, которую они совершили, умножает время отключения внешней поездки на максимальное количество отключений внутреннего контура. Чтобы получить правильный ответ, вам нужно учитывать, что подсчет поездки внутри цикла удваивается каждый раз, поэтому более поздняя поездка считается карликом более ранних.

Answer 2

Это на самом деле сложный вопрос. Технически ваше наблюдение правильное. Внутренний цикл будет выполнен до n раз, поэтому он выглядит как сложность O(n*log2(n)).

Но это не совсем так. Проблема заключается в том, что для первого выполнения while внутренний цикл for выполняется один раз, в следующий раз дважды, в следующий раз четыре раза и т. Д., До n/2 (округляется до следующей мощности двух, поэтому до n). Таким образом, он суммируется до 1+2+...n/2, который составляет O(n). То есть линейная сложность.

Answer 3

Для первой итерации внутренний цикл будет выполняться один раз, второй раз, для третьей итерации внутренний цикл будет выполняться 4 раза и так далее.Так

2^0 + 2^1 + 2^2 + 2^3 +.....+2^i where 2^i < n 

Мы можем найти i принимая log обе стороны 2^i < n, которая дает i=log2(n)

2^0 + 2^1 +...+2^(log2(n)) ie 2^0 + 2^1 + ...+ n 

Но

i < log2(n) and not i=log2(n). 

Таким образом, предыдущее значение n будет n/2

Итак, наконец, мы имеем

2^0 + 2^1...+n/2 

Доминирующий член n/2 поэтому его O (п/2), который является O (п)