Асимптотическая сложность простой функции псевдокода

Question

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

Входные данные: массив A, содержащий n целых чисел от A [1] до A [n] Выходные данные: двумерный n-by-n массив B, в котором B [i, j] для i

Answer 1

Отчасти зависит то, как вы реализуете add up array entries A[i] through A[j]:

for i = 1 to n
    for j = i to n
        sum = 0
        for k = i to j
            sum = sum + A[i]
        b[i,j] = sum
return b

Выше приведены O (n ^ 3) и Omega (n ^ 3), тета (n ^ 3). Однако, если вы подсчитаете sum по-другому:

for i = 1 to n
    sum = 0
    for j = i to n
        sum = sum + A[i]
        b[i,j] = sum
return b

Это O (n ^ 2), Омега (n ^ 2) и Тета (n ^ 2). На ваш конкретный вопрос - O и Omega, как правило, будут одинаковыми (то есть вы, как правило, получите границы тэты), если будете выполнять анализ во время выполнения, как в вашем вопросе, основанном на простом коде. Границы тета - это правило при рассмотрении конкретных реализаций, а не исключение.