Понятие алгоритма. Время работы алгоритма. 

Решаем задачу z:

Набор входных данных: m[n] , m[i]ℕ , nℕ, x

Постановка задачи: удалить из массива все числа, равные x

Набор выходных данных: m[k]

Число, описывающее размер входных данных: m[n] → (например) n

Набор допустимых (элементарных) операций.

- завести целую переменную

- присвоение значения целой переменной

- складывать целые переменные

- оператор if с операцией <

- обращение к массиву по индексу (по целой переменной)

- оператор goto  (с заданием меток)

 

Каждой операции si сопоставляется T(si) >0 – время выполнения операции (например =1)

 

Алгоритм: Процедура,  записанная в терминах допустимых операций

Алгоритм должен быть конечен. (не подразумевает ограниченность)

Алгоритм m решается некоторую задачу

 

Время работы алгоритма m на наборе входных данных In(m) = сумма времен выполнения всех элементарных операций

Определения верхних и нижних оценок времени работы алгоритма и решения задачи. 

Верхняя оценка времени работы алгоритма m: Φ(n): ℕ → ℕ :

nℕ : In(m): |In(m)≤n|: |T(m,In(m))|≤ Φ(n)

 

Нижняя оценка времени работы алгоритма m: φ(n): ℕ → ℕ :

n : In(m): |In(m)|=n: |T(m,In(m))|> φ(n)

   

    Верхняя оценка времени решения задачи z: Φ(n): ℕ → ℕ :

m – решения задачи, для которого Φ(n) – верхняя оценка времени работы

Нижняя оценка времени решения задачи z: φ(n): ℕ → ℕ :

n m решения задачи найдется In(m): |In(m)|=n: |T(m,In(m))|> φ(n)

Сведение задач и алгоритмов.

Задача z1g(n) z2 : nℕ, In(z1): |In(z1)|=n g: In(z1) → In(z2), | In(z2)|=n

и набор выходных данных задачи z2: Out(z2)→Out(z1) и все это за суммарное время ≤ g(n).

 

Теоремы о верхних и нижних оценках при сведении задач.

 

Теорема 1. z1g(n) z2, Φ2(n) – верхняя оценка времени решения задачи z2, то

Φ1(n)=Φ2(n)+g(n) – верхняя оценка времени решения задачи z1. 

 

Теорема 2. z1g(n) z2, φ1(n)   нижняя оценка времени решения задачи z1, то

φ2(n)=φ1(n)-g(n) –  нижняя оценка времени решения задачи z2.

n m2 решения задачи z2 найдется In(m2):

|In(m2)|=n: |T(m2,In(m2))|> φ2(n)=φ1(n)-g(n)

От противного: пусть это не так, т.е.

n m2 задачи z2: In(m2): |In(m2)|=n: |T(m2,In(m2))|≤  φ(n), То

m1 задачи z1 (= g+m2): In(m1): |In(m1)|=n: |T(m1,In(m1)|≤ φ2(n)+g(n) =

1(n)-g(n)+g(n)= φ1(n)

m1 задачи z1: In(m1): |In(m1)|=n: |T(m1,In(m1)|≤ φ1(n)

Противоречие с тем, что φ1(n) – нижняя оценка времени решения задачи z1

Ч.Т.Д.

Понятия O, o, Θ, Ω.

- f,g :ℕ → ℕ

f(n)=O(g(n)): n0ℕ, C>0 : n>n0: |f(n)|≤ C|g(n)| 

f(n)=o(g(n)): C>0: n0ℕ:  n>n0: |f(n)|≤ C|g(n)| 

f(n)=Θ(g(n)): n0ℕ, C1,C2>0 : n>n0:  C1|g(n)|≤  |f(n)|≤ C2|g(n)|

f(n)=Ω(g(n)): n0ℕ, C>0 : n>n0: |f(n)|> C|g(n)| 

Язык С. Время жизни и область видимости переменных в языке С. Локальные и глобальные переменные. Модель памяти языка С (стек, куча). Локальные автоматические массивы переменного размера в языке C. 

 

По времени жизни в С: статические, автоматические, динамические переменные

Статические: (в куче) рождаются в момент старта программы, умирают в момент завершения программы

Автоматические: (в стеке) рождаются в момент входа в блок, умирают – при выходе

 

Глобальны переменные: статические (вне функций; описываются с помощью слова extern)

int i=0; int f((int x){return x;}     |extern int i; extern int f(int x);

Локальные автом.переменные

static int x=0;//Локальная в файле

int f()

{int x=2; //локальная авт.

 {static int x=3;

 }

}

Локальны статич.переменные