Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Сезон 2003 - 2004
Сезон 2002 - 2003
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Сезон 2001 - 2002
Сезон 2000 - 2001
Задача 2 - СТАТИСТИКА - Анализ

Стана традиция една от задачите в задочната част на Конкурса на PC Magazine да е посветена на ефективнатата организация на данните. Когато в някакво приложение се поддържат големи обеми от данни, ефективността на имплементацията на обичайните опeрации - за добавяне, изтриване и търсене, както и на специфичните операции на приложението е от голямо значение. Статистически, всяка една от операциите се изпълнява достатъчно често и неефективността на само една от тях може да компрометира цялото приложение.

Да вземем за пример Конкурсната задача с номер 2 - Статистика. Да означим с N броя на съхраняваните в определен момент характеристики. Ако за запазване на данните (множество от естествени числа) използваме масив, в който да ги добавяме в реда на регистрирането им в структурата, като новопостъпилата характеристика винаги отива на първото свободно място в масива. Oперацията добавяне ще се изпълнява много бързо (сложност O(1)). Изтриването на характеристика, обаче, както и намирането на броя на характеристиките в зададен интервал изискват преглеждане на всички елементи на масива и като цяло сложността на една "средно статистическа операция" на приложението ще бъде O(N). Ако решим да съхраняваме текущо регистрираните характеристики в сортиран вид, тогава с помощта на двоично търсене намирането на броя на характеристиките в зададен интервал може да бъде редуцирано до O(log2N) стъпки, но вмъкването на нова характеристика и изтриването на съществуваща ще запазят средната сложност на операция на О(N). Общата идея в подобен род приложения е не да се подобрява колкото може сложността на една операция (или на част от операциите) за сметка на останалите, а да се търси такава организация на данните, че сложността на "най-лошата" операция да е колкото може по-добра - амортизирана сложност. Традиционен подход за подобряване на амортизираната сложност са различните дървовидни структури.

Първообраз на всички подобни структури е добре известното дърво за двоично търсене, с помощта на което всички класически операции се имплементират със сложност O(h), където h е височината на дървото. Неприятното е, че добавянето и изтриването на елементи може да дебалансира структурата, т.е. височината й да нарастне доста в сравнение с минимумa от log2N, и изпълнението на операциите да се забави. Решението на този проблем е дървовидната структура непрекаснато да се подлага на "балансиране", когато това се налага. Така текущата височина на дървото се държи близо до теоретичния минимум и операциите остават бързи.

Най-известните форми на балансирани дървета за двоично търсене са така наречените AVL (от имената на създателите на структурата Адельсон-Вельский и Ландис) и Red-Black (или RB, заради оцветявянето на върховете в два цвята и използването на оцветяването като критерий за проверка баланса на дървото). Не е случайно, че повечето от участниците и по-специално победителите са се насочили към тези две структури (които са и най-добре описани в литературата, виж например Cormen, Leiserson, Rivest, Introduction to Algorithms) или към някакви други, повече или по малко познати форми на балансиране на дървото за двоично търсене.

Особеното в задача 2 е операцията за търсене на броя на елементите на структурата в зададен интервал, която не е присъща на балансираните дървета за двоично търсене. За имплементирането на тази операция с логаритмична сложност е необходимо да се направи не сложна модификация, която за случая с RB дървета е описана в посочената вече книга. Да се спрем малко по подробно на тази модификация.

Към обичайните за всяко дърво за двоично търсене полета key, parent, left и right да добавим в записа на всеки връх X полето size, което ще съдържа брoя на върховете в поддървото с корен Х, включително и корена. Поддържането на това поле при изпълнението на операциите за добавяне и изтриване (и неизбежното пребалансиране на дървото) ще бъде със сложност O(log2N). За целта е необходимо само да се нанесат необходимите поправки в полетата size на всички върхове по пътя от мястото където е настъпило изменението до корена на дървото.

Колкото до операцията за намиране броя на запомнените характеристики в зададен интервал [A,B], тя също се имплементира с логаритмична слойност. За целта първо намираме в дървото записът, чийто ключ Х е най-големият, който е по-малък или равен на B и съответно записът, чийто ключ Y е най-малкият, който е по-голям или равен на А. Да означим с pX и pY съответните записи. Тогава търсеният брой характеристики в интервала [A,B] е 1+ pX.left.size - pY.left.size.

Анализи на решения изпратени от участници:

  • Владимир Молотков

  • За въпроси можете да ни пишете на адрес: konkurs@musala.com.

    Supported by Musala Soft Ltd.

    Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.