Алгоритмлар ва маълумотлар тузилмаси Алгоритмларнинг мураккаблигини таҳлил қилиш

Алгоритмлар ва маълумотлар тузилмаси Алгоритмларнинг мураккаблигини таҳлил қилиш

Алгоритмлар ва маълумотлар тузилмаси

Алгоритмларнинг мураккаблигини таҳлил қилиш

Маъруза саволлари

• 
  Алгоритмларнинг мураккаблигини таҳлил қилиш
  
• 
  Вақт бўйича мураккаблик
  
• 
  Асимптотик мураккаблик
  

Кўпгина масалаларни ечиш учун турли хил алгоритмлар мавжуд.

Аниқ масалани ечиш учун улардан қайси бирини танлаш лозим?

Мураккабликни таҳлил қилиш ишлаш вақти ва ҳажмини баҳолаш учун керак бўлади, яъни

Мураккабликни таҳлил қилиш ишлаш вақти ва ҳажмини баҳолаш учун керак бўлади, яъни

Бажарилиш учун алгоритмга қанча вақт керак бўлади.

• 
  Бажариш учун қанча ресурс керак бўлади.
  

Алгоритмларнинг мураккаблигини нимада баҳолаш мумкин?

Алгоритмларнинг мураккаблигини нимада баҳолаш мумкин?

Алгоритм мураккаблигини минут, секундлада ўлчаш мумкин. Аммо…

Алгоритмнинг бажарилиш вақти процессор частотаси, процессор архитектурасига боғлиқ.

Бир хил алгоритм ҳар хил компьютерларда ҳар хил вақтда бажарилади.

Бажарилган амаллар билан ўлчаш мумкин.

Бажарилган амаллар билан ўлчаш мумкин.

Амал деб нимани олиш мумкин?

Масалан.

Иккита сонни қўшиш битта амалми?

Агар сон 64 бит, процессор 32 бит бўлса, 3 та амал бўлади.

Амаллар сони аниқ тушунча эмас.

Дастур нечта амал бажариши кирувчи n ларга боғлиқ.

Дастур нечта амал бажариши кирувчи n ларга боғлиқ.

Дастурнинг бажарилиш вақтини амаллар сонига кўра қуйидагича баҳолаймиз :

Бу дастурларнинг қайси бири «яхшироқ» ???

N нинг қийматига боғлиқ.

• 
  N нинг қийматига боғлиқ.
  
• 
  n нинг кичик қийматларида ҳамма дастур бир хил ишлайди. Бу муаммо катта n ларда вужудга келади.
  
• 
  n (n2, n3 …) нинг даражаси коэффициентга қараганда катта рол ўйнайди.
  
• 
  n4 лик дастур n3 га қараганда ёмонроқ ишлайди.
  

n, n2 , n3 , ва 2n амалда ишловчи дастурлар бўлсин.

• 
  n, n2 , n3 , ва 2n амалда ишловчи дастурлар бўлсин.
  
• 
  Дастур ишлайдиган маълумотлар ўлчамини 10 баробарга орттирамиз.
  

  Дастур неча маротаба секинроқ ишлайди?

n	10 марта ортади	1-дастур
n2	100 баробар ортади	2-дастур
n3	1000 марта ортади	3-дастур
2n	Агар 10 га бўлса у ҳолда 1024 га Агар 10 марта бўлса у ҳолда баҳолаш қийин	4-дастур

Если nk , где к некоторая константа, то говорят, что программа работает за полином. Или полиномиальное время работы.

• 
  Если nk , где к некоторая константа, то говорят, что программа работает за полином. Или полиномиальное время работы.
  
• 
  Если 2n (аn ) , где к некоторая константа, то говорят, что программа работает за экспоненциальное время.
  

Яна мисол

Чем объяснить???

Хулоса.

Хулоса.

Алгоритм томонидан сарф қилинган элементар амаллар сони нафақат кирувчи маълумотларнинг ўлчамига, балки маълумотларнинг ўзига ҳам боғлиқ.

Алгоритмнинг ишлаш вақти қуйидагиларга боғлиқ:

• 
  Кирувчи маълумотларнинг ўлчами.
  
• 
  Маълумотларнинг ўзи.
  

Ҳисоблашлар мураккаблиги назарияси

Ҳисоблашлар мураккаблиги назарияси

Қуйидаги эҳтиёжлар туфайли келиб чиққан:

• 
  Алгоритмларнинг тезкорлигини таққослаш;
  
• 
  Уларнинг ҳатти ҳаракатини аниқ тавсивлаш.
  

Керакли тушунчалар

Ҳисоблаш мураккаблиги- алгоритм томонидан вақт ёки фазо ресурсларидан фойдаланилиши.

Алгоритмнинг бажарилиш вақти масалани ечиш учун керак бўладиган элементлар қадамлар сони билан аниқланади ва кирувчи маълумотлар ўлчамига боғлиқ бўлади.

Фазо – алгоритм томонидан қўлланиладиган хотира ҳажми (фазовий мураккаблик).

Анализ алгоритмов

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

При оценке алгоритма исходят из количества наиболее значимых для данного алгоритма операций, выполняемых в ходе его работы.

Алгоритмни таҳлил қилиш

Алгоритмнинг бажарилиш вақтини таҳлил қилишнинг умумий методологияси:

1. Алгоритмнинг псевдокодда таърифи.

2. Псевдокоднинг тузилмасини таҳлил қилиш асосида амаллар сонини аниқлаш.

3. Алгоритмнинг умумий амаллар сонини аниқлаш.

Аналитик ёндашув

• 
  Алгоритмни дастурлаш тилининг бирида ёзиб олиш.
  

  2. Дастурни машина буйруқларига ўтказиб олиш.

  3. Ҳар бир машина буйруғи учун бажарилиш вақтини аниқлаш.

ПМисол.

ПМисол.

Функциянинг ўсишлари

Временная сложность алгоритмов сортировки

http://fayllar.org