QFindStat5(A,1,N,k)

Если N £ 5 то найти медиану x любым методом; return x

Разбить массив A[1…N] на пятерки элементов и

Отсортировать элементы внутри пятерок

x= QFindStat5 (A^’,1,[(N+4)/5], ([(N+4)/5]+1)/2), где A^’ – массив медиан пятерок

Выполнить один шаг QuickSortP для псевдомедианы x

=> массив разбит на куски длиной L и N-L

Если k £ L то return QFindStat5 (A,1,L,k)

иначе return QFindStat5 (A,L+1,N,k)

Теорема. Время работы алгоритма QFindStat5 равно Q(N), где N – количество элементов в обрабатываемом массиве.

Доказательство. В массиве медиан пятерок [(N+4)/5 ] элементов. Нахождение медианы x этого множества гарантирует, что в каждой пятерке справа от x, включая пятерку с x (см. рисунок ниже), и кроме последней пятерки, 3 элемента больше или равны x (на рисунке эти элементы выделены серой областью). Количество всех указанных пятерок не менее [([(N+4)/5]+1)/2], последняя пятерка может быть не полной и в ней, в худшем случае, может быть всего один элемент больше или равный x. Если теперь исключить из описанного множества x, то получается, что мы имеем 3[([(N+4)/5]+1)/2] - 3 элементов больше или равных x. Легко показать, что такое же количество элементов меньше или равны x. Т.о. после выполнения одного шага QuickSortP останется не более N - 3[([(N+4)/5]+1)/2] + 3 £ N – 3N/10 + 3 = 7N/10 + 3 элементов.

Оценим время выполнения алгоритма QFindStat5: T(N). Оно складывается из времени поиска медианы медиан пятерок элементов (T([(N+4)/5])), времени поиска медианы в отрезанном куске множества длиной не более 7N/10 + 3 (T(7N/10 + 3)) и всего остального (O(N)).

T(N) £ T(N/5+1) + T(7N/10 + 3) + O(N)

Теперь, если предположить, что T(i) £ c i, для i<N, то получим

T(N) £ с(N/5+1) + с(7N/10 + 3) + O(N) £ с(9N/10 + 4) + O(N) =

= сN + (O(N) – c(N/10 - 4))

Выбрав достаточно большое c получим, что для N>40

O(N) – c(N/10 - 4) £ 0

Далее, выбрав еще большее c можно получить, что для N£40

T(N) £ сN

Т.о. мы получим, что T(N) £ сN для любого N.

¢

Язык программирования C.

  Б.В. Керниган, Д.М. Ричи. Язык программирования С.

Переменные

Основные типы

В языке С есть две основные разновидности базовых типов: целые и вещественные. К целым типам относятся типы

Char

Short

Int

Long

Перед каждым вышеупомянутым типом может присутствовать слово signed или unsigned. Идентификатор signed указывает на то, что переменная имеет знак, а unsigned – на отсутствие знака у переменной. По умолчанию, все переменные имеют знак. Исключением является переменная типа char. Полагаться на наличие/отсутствие знака у переменной данного типа нельзя, т.к., как правило, данное свойство может быть изменено с помощью ключей компилятора.

Известно, что в данном списке указанные типы располагаются по неубыванию их размеров. Если требуется узнать конкретный размер переменной в байтах, то он может быть получен с помощью оператора sizeof(): sizeof(char).

К вещественным типам относятся

Float

Double

Известно, что sizeof(float) £ sizeof(double).

Кроме базовых типов, существуют производные типы, задающиеся с помощью понятий массив, указатель, функция, структура, объединение.

Базовые понятия

Ø описание и определение

Ø время жизни

Ø область видимости или область действия

Одними из основных понятий программирования являются описание и определение объектов.

Описание переменной задает ее тип и указывает на то, что переменная где-то определена. Признаком описания переменной служит наличие ключевого слова extern перед оператором, ее задающим. Отсутствие ключевого слова extern говорит об определении переменной.

Определение переменной указывает место в программе, задающее время рождения переменной. При определении переменной можно задать инициализирующее ее значение. Определение переменной всегда является ее описанием.

В программе может быть сколько угодно согласующихся описаний одной и той же переменной, но должно быть ровно одно ее определение.

Время жизни переменной задается интервалом между моментом рождения переменной и моментом ее смерти. Внутри этого интервала гарантируется сохранность значения переменной, т.е. значение переменной может быть изменено только с помощью соответствующих операторов программы (естественно, это верно только в случае правильно написанной программы). С точки зрения времени жизни, в языке С бывает два вида переменных: статические и автоматические.

Автоматические переменные всегда определяются внутри некоторого блока. Блоком называется часть тела некоторой функции, заключенная в фигурные скобки. Телом функции называется набор операторов, задающих действия, совершаемые функцией. В частности, тело функции также является блоком. Автоматические переменные всегда являются локальными, т.е. их область видимости ограничивается их блоком. Автоматические переменные рождаются в момент входа выполнения программы в данный блок и умирают в момент выхода из блока.

Внутри одного блока могут быть другие блоки и если во внутренних блоках определить переменные с именами, совпадающими с именами переменных во внешних блоках, то внутренние имена переменных перекроют видимость для внешних переменных. Перекрытие области видимости не сказывается на времени жизни переменных.

Автоматические переменные разрешается определять только в начале блока, перед выполняемыми операторами.

Автоматические переменные используют память, выделяемые в системном стеке, что делает процедуру отведения/очистки памяти под них весьма быстрой. Однако, как правило, системный стек имеет ограниченный размер и, поэтому, нельзя создавать автоматические переменные слишком большого размера. Причиной переполнения стека (stack overflow) может также служить бесконечная рекурсия, случайно созданная в программе.

Статически созданные переменные рождаются в момент запуска программы и умирают в момент прекращения работы программы. Память под них отводится в общей куче (heap), т.е. в обще-используемой памяти. Ее размер ограничивается размером памяти, доступной программе. Статически созданные переменные это – либо глобальные переменные (т.е. переменные, определенные вне всех блоков программы), либо локальные

Осталось упомянуть о внешних статических переменных – глобальных переменных, область видимости которых ограничена данным файлом. Как и все глобальные переменные, эти переменные определяются вне всех блоков программы, но перед их определением написано ключевое слово static.

Если есть несколько переменных с одинаковым именем, то внешние статические переменные перекрывают область видимости соответствующих глобальных переменных, а локальные переменные перекрывают область видимости соответствующих внешних статических переменных.

Изначально в языке С присутствуют регистровые переменные. Наличие ключевого слова register перед определением переменной служит указанием компилятору использовать внутренние машинные регистры для хранения данной переменной. На данный момент, при использовании оптимизирующих компиляторов наличие данного типа, как правило, не может служить для ускорения работы программы. Более того, обязательное использование регистра для хранения данной переменной запрещает его использование для других целей, что может послужить поводом к замедлению работы программы.

Следует упомянуть, что, как правило, использование глобальных переменных является дурным стилем программирования. Их наличие существенно усложняет дальнейшее развитие программы и слияние написанной программы с другими, отдельно написанными кусками.

---

Дата добавления: 2015-10-30