Структура данных и алгоритма. Ч1

Data Structures and Algorithms


Асимптотический анализ

Измерение сложности алгоритмов - анализ времени, которое потребуется для обработки данных.При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.

Основные оценки роста, встречающиеся в асимптотическом анализе:

  • Ο (Ο-большое) – верхняя асимптотическая оценка роста временной функции;
  • Ω (Омега) – нижняя асимптотическая оценка роста временной функции;
  • Θ (Тета) – нижняя и верхняя асимптотические оценки роста временной функции.

Пусть n – величина объема данных. Тогда рост функции алгоритма f(n) можно ограничить функций g(n) асимптотически:

Обозначение Описание
f(n) ∈ Ο(g(n)) f ограничена сверху функцией g с точностью до постоянного множителя
f(n) ∈ Ω(g(n)) f ограничена снизу функцией g с точностью до постоянного множителя
f(n) ∈ Θ(g(n)) f ограничена снизу и сверху функцией g

Например, время уборки помещения линейно зависит от площади этого самого помещения (Θ(S)), т. е. с ростом площади в n раз, время уборки увеличиться также в n раз. Поиск имени в телефонной книге потребует линейного времени Ο(n), если воспользоваться алгоритмом линейного поиска, либо времени, логарифмически зависящего от числа записей (Ο(log2(n))), в случае применения двоичного поиска.

Для нас наибольший интерес представляет Ο-функция. Кроме того, в последующих главах, сложность алгоритмов будет даваться только для верхней асимптотической границы.

Под фразой «сложность алгоритма есть Ο(f(n))» подразумевается, что с увеличением объема входных данных n, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n).

Важные правила асимптотического анализа:

Ο(k*f) = Ο(f) постоянный множитель k (константа) отбрасывается, поскольку с ростом объема данных, его смысл теряется, например: Ο(9,1n) = Ο(n)
Ο(f*g) =Ο(f)*Ο(g) оценка сложности произведения двух функций равна произведению их сложностей, например:
Ο(5n*n) = Ο(5n)*Ο(n) = Ο(n)*Ο(n) = Ο(n*n) = Ο(n2)
Ο(f/g)=Ο(f)/Ο(g) оценка сложности частного двух функций равна частному их сложностей, например:Ο(5n/n) = Ο(5n)/Ο(n) = Ο(n)/Ο(n) = Ο(n/n) = Ο(1)
Ο(f+g) равна доминанте Ο(f) и Ο(g)оценка сложности суммы функций определяется как оценка сложности доминанты первого и второго слагаемых, например:Ο(n5+n10) = Ο(n10)

Порядок роста

Порядок роста описывает то, как сложность алгоритма растет с увеличением размера входных данных. Чаще всего он представлен в виде Ο-нотации (от нем. «Ordnung» — порядок) : Ο(f(x)), где f(x) — формула, выражающая сложность алгоритма. В формуле может присутствовать переменная n, представляющая размер входных данных.

Константный — Ο(1)

Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных. Следует помнить, однако, что единица в формуле не значит, что алгоритм выполняется за одну операцию или требует очень мало времени. Он может потребовать и микросекунду, и год. Важно то, что это время не зависит от входных данных.

Линейный — O(n)

O(n) — линейная сложность
Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

Логарифмический – O( log n)

O(log n) — логарифмическая сложность
Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

Линеарифметический — O(n·log n)

Линеарифметический (или линейно-логарифмический) алгоритм имеет порядок роста O(n·log n). Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию. В следующих частях мы увидим два таких примера — сортировка слиянием и быстрая сортировка.

Квадратичный — O(n2)

O(n2) — квадратичная сложность
Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n, т. е. n2.

Наилучший, средний и наихудший случаи

Что мы имеем в виду, когда говорим, что порядок роста сложности алгоритма — O(n)? Это усредненный случай? Или наихудший? А может быть, наилучший?

Обычно имеется в виду наихудший случай, за исключением тех случаев, когда наихудший и средний сильно отличаются. К примеру, мы увидим примеры алгоритмов, которые в среднем имеют порядок роста O(1), но периодически могут становиться O(n) (например, ArrayList.add). В этом случае мы будем указывать, что алгоритм работает в среднем за константное время, и объяснять случаи, когда сложность возрастает.

Самое важное здесь то, что O(n) означает, что алгоритм потребует не более n шагов.

Сложность основных алгоритмов сортировки и работы с данными

Источники:
https://tproger.ru/translations/algorithms-and-data-structures/
https://tproger.ru/articles/computational-complexity-explained/
http://kvodo.ru/asymptotic-analysis.html

Дополнительные полезные материалы:
https://www.lektorium.tv/lecture/13926

Нравиться? Жми сюда!

Установка Android Studio. Hello world.


В качестве варианта среды разработки под мобильные устройства, возможно использование Android Studio.
Здесь будет выложена установка и создание простого приложения для телефона.
--Читать далее...

Нравиться? Жми сюда!

ООП и Java. Объект, класс.

https://j.livelib.ru/boocover/1000611610/o/afda/Bryus_Ekkel__Filosofiya_Java.jpeg

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

Разбираясь с основами ООП, для большего понимания материала, я обратился к литературе и ознакомился с книгой Брюса Эккеля «Философия java». В первой главе-введении, он дает простые определения основам, для дальнейшего манипулирования далее этими понятиями. Далее приведены вырезки из разделов главы.
Читать дальше...

Нравиться? Жми сюда!

Применение модели Захмана. Проектировании ИТ-архитектуры предприятия.

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

Нравиться? Жми сюда!

5 правил работы с суммами или live example к разговору о множестве чисел с плавающей точкой

В современном программном обеспечении очень часто возникает необходимость выполнять различные операции с всевозможными суммами денег. Однако до сих пор мне нигде не попадалось документации, в которой были бы сведены воедино основные правила представления сумм и реализации финансовых вычислений. В этой статье я попробую сформулировать те правила, которые составил сам на основании личного опыта.
Читать далее 5 правил работы с суммами или live example к разговору о множестве чисел с плавающей точкой

Нравиться? Жми сюда!

Производственная практика.

(Летний длиннопост)

26.06.2017 — День первый

Первый день на предприятии.
Восемь утра. Тёплое восходящее из-за гор солнце, медленно поднимающееся над долиной. Другой конец города, до этой поры незнакомый, где меня встретили гигантские синие ворота, грозная проходная с охранниками и высокий забор, обрамлённый "Егозой": просто так не пройти! Хорошо, что меня ждали..)
После регистрации на проходной мне открылся удивительный организованный мир "ПО «ТРЕК»".

Читать далее Производственная практика.

Нравиться? Жми сюда!

Перевод статьи(5)

Общее число гепардов резко стремится к исчезновению

Легкий, аэродинамичный и способный развить скорость 60 миль в час (97 км/ч) всего за несколько шагов. Ни одно существо не может покрыть землю так как гепард. И не только самое быстрое в мире наземное животное, могучий, быстрый от природы, бывает и забредает дальше, чем любой другой хищник. Но это вызывает проблемы в мире, где деятельность человека продолжает сталкиваться с жизненно важными местами обитания диких животных.

В настоящий момент гепарды названы "Уязвимыми" Международным союзом для Сохранения Природы и Природных ресурсов. Но новое исследование, выполненное исследователями от Зоологического Общества Лондона (ZSL), Wildlife Conservation Society (WCS) и организацией по охране природы кошки Panthera, принудило авторов призвать, чтобы их статус был в скором времени обновлен до "Подвергаемого опасности", статус, который принес бы более высокий уровень международной поддержки сохранения вида.
Гепард1

"Это исследование представляет самый всесторонний анализ статуса гепарда до настоящего времени",&mdash говорит доктор Сара Дюрант. "Учитывая скрытную природу этой неуловимой кошки, было трудно собрать достоверную информацию о разновидностях. Наши результаты показывают, что большие космические требования для гепарда, вместе со сложным рядом угроз, с которыми встречаются разновидности в дикой природе, означают, что они, вероятно, будут намного более уязвимыми для исчезновения, чем ранее считалось".

Уход за кошками в охраняемых заповедниках &mdash это одно, но сохранитm их, когда они бродят за пределами &mdash конечно другое. Исследователи говорят, что 77% из оставшихся гепардов обитают за пределами охраняемой территории, где животные более чувствительны к антропогенному воздействию, таким как потеря добычи из-за чрезмерной охоты, потеря мест обитания из-за изменений в землепользовании и незаконного вывоза гепардов и тигрят как экзотических животных.
Гепард2

Отчет Би-би-си ранее в этом году показал серьезность этой жестокой формы торговли дикой природой, когда все пометы были изъяты у их матерей и их продали на черном рынке. Наличие покупателей в Персидском заливе обусловлено тем, что они делают покупки, которые затем становятся игрушками. Это выглядит еще более бессмысленно, когда рассматривают число от Фонда сохранения Гепардов, где указывается, что около 1200 детенышей гепарда переправляются из Африки за последнее десятилетие, около 85% из них умирает во время путешествия.

В Зимбабве сочетание этих факторов уменьшает число гепардов от 1200 до максимум 170 в 16 лет, потеря населения составляет 85%. Исследователи говорят, что азиатские гепарды, оставшиеся в изолированном Иране, пострадали больше всего, .
Гепард3
Все это побудило исследователей призвать к срочной перестройке в стратегии охраны гепардов. Они говорят, что есть потребность работать целостным подходом, который идет вне национальных границ и предлагают стимулы для местных сообществ защитить гепардов и продвинуть стабильное сосуществование дикой природы.

"Мы поражены как близки гепарды к исчезновению", &mdash заявляет директор Cheetah Programme Пантеры, доктор Ким Янг-Овертон. "Основным выводом из этого исследования является недостаточность обеспечения территорий охраной. Мы должны мыслить более масштабно, сохранить всю мозаику защищенных и незащищенных пейзажей, где обитают эти далеко забредающие кошки, если мы хотим предотвратить потерю гепардов навсегда.

Зоологическое Общество Лондона выпустило коллекцию красивых фотографий гепардов, чтобы выступить с объявлением, которое Вы можете проверить в галерее. Исследование опубликовано на сайте Proceedings of the National Academy of Sciences.
Оригинал статьи

Нравиться? Жми сюда!

Перевод статьи(4)

Беспилотники регулируют движение блуждающих слонов подальше от опасности

СлоныБеспилотники уже играют определенную роль в сохранении африканской дикой природы, ведется изучение того, как самолет может быть использован в качестве средства для наблюдения, чтобы поймать и удержать браконьеров. Но новое исследование предполагает, что дроны могут помочь спасти слонов не только от горе-охотников, но и отпугивать самих слонов.
Слоны создают проблему для сельских общин в Танзании, когда они покидают парк в поисках пищи, такой как кукуруза и арбузы. Беда в том, что продукты принадлежат трудолюбивым фермерам, которые полагаются на урожай, чтобы прокормить свои семьи.
Это заставляет фермеров отпугивать животных, бросая камни и стуча в барабаны. Но их тактика включает также более отчаянные меры, как швыряние петард, отравления зерном, браконьерские банды убивают животных на слоновую кость. В некоторых частях Африки такого рода конфликт с фермерами на самом деле представляет большую угрозу для слонов, чем само браконьерство.
Но более мирный способ борьбы с этими противостояниями представился еще в 2014 году, когда исследователи из "Решений для Биоразнообразия и Дикой природы" танзанийского Научно-исследовательского института Дикой природы (TAWIRI) и Проекта Мары Элефэнт и Mara Elephant Project заметили, что наличие поблизости беспилотных летательных аппаратоы (БПЛА) заставляет слонов бежать.
Команда приступила к проверке этой гипотезы через 51 полевое испытание в полосе вдоль границы Тарангире в Танзании и национальном парке Серенгети. Они обнаружил, что беспилотники, которые стоят около $800 за штуку, могут быть использованы для отпугивания диких слонов из культур как днем, так и ночью. Рейнджеры, работающие в этих парках, использовали тактику более чем 120 раз, в ответ на призывы со стороны сообщества по поводу так называемого Конфликта слонов и людей. Их исследования уже сообщалось в журнале "Орикс".
"Мы подчеркнули важность сбора данных на протяжении всего этого проекта", &mdash говорит ведущий автор статьи Натан Хан. "Иногда мы склонны преувеличивать мощь новых технологий, и мы хотели справедливо оценить полезность дронов для транспортировки слонов из культур и других областях. Результаты очень положительные и показывают, что беспилотники могут быть эффективными помощниками для менеджеров дикой природы".
В то время как слоны могут в конечном счете привыкнуть к гудящим беспилотникам и больше не бояться их, исследователи говорят, что не видели признаков этого эффекта. Но они действительно отмечают, что метод мог также оказаться полезным в выпаске другой дикой природы с рейнджерами, использующими беспилотники, например, чтобы сопроводить раненого быка, чтобы ветеринары могли обработать его рану.
"Большее расстояние взаимодействия, которое обеспечивают беспилотники, предоставляет необходимую безопасность для наших рейнджеров, фермеров и слонов," &mdash объясняет Анджела Мвакэтоуб, глава руководства исследованиями в TAWIRI и соавтор исследования. "Вот полезная технология, которую мы не имели в нашем наборе инструментов один год назад".
Оригинал статьи

Нравиться? Жми сюда!

Перевод статьи(3)

Вера Рубин, "мать" темной материи, скончалась

Вера Рубин, астроном, работа которой подтвердила существование темной материи, скончалась в возрасте 88 лет. Наряду с этим инновационным открытием, Рубин оставила в наследие научные достижения и премии, и была ярым сторонником женщин в науке.
Вера Рубин

Темная материя, или по крайней мере идея, что некоторая невидимая сила влияет на массу галактик, теоретизировалась уже в 1920-х, но только в работе Рубин в 1960-х и 70-х её существование было подтверждено. Она и её коллега Кент Форд, наблюдая, как быстрые звезды и газы вращаются вокруг галактического центра на различных расстояниях, изучали распределение массы в самом близком соседе Млечного пути, галактике Андромеде, .

Но орбиты не выстраивались в соответствии с Ньютоновской гравитационной теорией, и после изучения других галактик, команда решила, что одна только видимая масса не может составлять звездные движения. Ранее неизвестный материал был предложен, назван "темная материя" вследствие того, что он не испускает, не поглощает или не отражает свет. Это странное вещество, как полагают, составляет более чем 90% Вселенной, и поиск субатомной ответственной частицы продолжается по сей день.

Кроме руководства этой областью исследования, Рубин оставила в наследство содействие расширению прав и возможностей женщин входить в доминируемые мужчинами арены науки. Она была первой женщиной, допущенной к использованию инструментов в Паломарской обсерватории, и она работала, чтобы увеличить количество женщин в корпусах как Национальная академия наук (NAS), так и в академиях в целом.

"Вера была удивительным ученым и удивительным человеком", &mdash говорит Нета Бэхкол, коллега Рубин из Принстонского университета. "Новаторский астроном, 'мать' плоских кривых вращений и темной материи, чемпион женщин в науке, наставница и образец для подражания для целых поколений астрономов".

Вера Рубин родилась 23 июля 1928 и скончалась 25 декабря 2016 в Принстоне, Нью-Джерси.

Оригинал статьи

Нравиться? Жми сюда!

Перевод статьи(2)

Более безопасный, более умный Suzuki Swift дюбитирует в Женеве

Suzuki мог бы быть относительно небольшим производителем по сравнению с подобными Mazda и Subaru, но маленький Swift всегда был достаточно хорош, чтобы поднять его до более крупных детей в детской площадке. Больше чем 5.3 миллионов были проданы, так как автомобиль первого поколения, появившийся в 2004, завоевал поклонников своим милым дизайном и простым управлением. Теперь есть новый с новым обликом и большим количеством технологии.
Swift1

Обновленный Swift 2017 года оснащен более легкой, более жесткой новой платформой, названной Heartect. Вместе с 1.0-L стандартом двигателя BoosterJet с турбинным двигателем в RS Swift, должен появиться небольшой люк, хотя увлеченные водители будут скрещивать пальцы и надеяться, что Sport Swift будет предлагаться. Двигатель в RS вместе с автоматической коробкой передач с шестью скоростями без упоминания о рычаге переключения передач.

Наряду с компактным турбо, будут также предлагаться 1.2-L двигатель без наддува и умеренный гибрид, но детали об этих трансмиссиях встречаются редко. Ожидаются больше деталей, когда автомобиль уже получит свой глобальный запуск на Женевском Автосалоне в марте.
Swift2
Как и следовало ожидать от нового автомобиля, нацеленного на молодых покупателей, в Swift будет загружена умная техника безопасности. Благодаря новой камере и лазерному датчику, установленным на передней части автомобиля, он будет автоматически тормозить, если чувствует предстоящее столкновение, и опускать фары, когда он чувствует встречный автомобиль. Адаптивный круиз-контроль тоже в списке вариантов обновлений.

Если, так или иначе, несчастный случай произойдет со всем этим набором усовершенствований, новая платформа должна помочь сделать автомобиль безопаснее при столкновении.

Оригинал статьи

Нравиться? Жми сюда!