Лучше бы перевели что-то другое

Я считаю принципиально неправильным подавать материал с ошибками. Можно показать «на пальцах» (я показал как) и при этом не написать непонятно что.

пс я не математик, лишь compueter science окончил, но мне неприятно видеть когда пишут муть, которая только сбивает с толку(как мне кажется). Вон выше уже одна жертва есть (считающая, что log1/2 1/4 = 1/2)

Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. http://habrahabr.ru/post/195996/

это хабра, детка. Привыкай. И поставь плюсик аффтору. Потому-что обычно он ВНЕЗАПНО даже прав — действительно, логарифм на практике обычно НАМНОГО меньше числа. Я даже слегка удивлён...

PS: хотя лучше не читай хабру вообще, если ты в школе учился. Береги свои нервы.

А разве не так?

вообще-то нет.

(1/2)^2 == 1/4

откуда log(1/4) == 2 (по основанию 1/2)

2 в восемь раз больше 1/4.

Во-вторых, он же там пишет

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

Это ОНА, блжад!

да, сделай доброе дело, если ты на быдлохабре зареган:

1. то, что она пытается объяснить, называется «дихотомия», и объясняется на пальцах, гуглится на раз, по словам «как поймать льва в пустыне?» Вот например: http://lurkmore.to/Как_поймать_льва_в_пустыне А «бинарный поиск» это вообще говоря несколько иное.

2. пусть немного почитает про О-большое. Есть русская литература по этой теме. Или путь своё О-большое использует по назначению, и не пишет больше всякий бред на хабру.

Ой, лучше бы промолчал

Ты кстати, почитал про это O у неё? Почему оно выглядит там как тета или скорее как буква из бирманского языка?

не, обычная тета, греческая. 0xCE98. То-ли она просто дура, то-ли пиратский скан какой-то книжки читала...

Во-первых, не всякая фраза, содержащая "- это" — это определение, как тут половина отметившихся почему-то считают. Поэтому придирка про то что «под это попределение подпадают другие функции» - пустая.

я знаю. Например фраза «У моей подруги с её парнем было ЭТО» определением никак не является. Вот только здесь за такое скор режут, а темы в мусорку.

Во-вторых, он же там пишет, что его только двоичный логарифм интересует. И он явно очень хотел обратить внимание читателя на факт его «медленного» роста.

кстати, именно двоичный логарифм — «самый быстрый» из всех логарифмов с целым основанием.

кстати, для O-большого нет никакой разницы, КАКОЕ там основание, лишь-бы было чуть больше 1.

Кстати, IRL алгоритмы с логарифмической асимптотой сходятся быстро далеко не всегда, а иногда не сходятся вовсе.

Да, детки, ВНЕЗАПНО. У меня для вас и пруф есть: девочка искала числа в массиве «бинарным поиском», а вы попробуйте не искать, а просто поделить. Да, дихотомией. Поделили? Логарифмическая сложность? А теперь попробуйте знаменатель =0.

Что, детки? Делить на ноль нельзя? А как это следует из этого очередного хабравысера? Из него как раз следует, что

Практическая рекомендация: улучшение асимптотического времени выполнения программы часто чрезвычайно повышает её производительность. Намного сильнее, чем небольшая «техническая» оптимизация в виде использования более быстрого языка программирования.

Далее, детишки:

factorial Давайте проанализируем эту функцию. Она не содержит циклов, но её сложность всё равно не является константной. Что ж, придётся вновь заняться подсчётом инструкций. Очевидно, что если мы применим эту функцию к некоторому n, то она будет вычисляться n раз. (Если вы в этом не уверены, то можете вручную расписать ход вычисления при n = 5, чтобы определить, как это на самом деле работает.) Таким образом, мы видим, что эта функция является Θ( n ).

ну во первых, рекурсия это тоже цикл. Ну ладно, не важно. Самое смешное в другом — сложность вычисления факториала растёт совсем не как O(n), а намного быстрее. НАМНОГО. Почему? А потому, что сложность самого умножения логарифмическая, а факториал растёт как известно куда как быстрее, чем любая степенная функция. Так-то...

Особенно понравилось:

Как только вы проанализировали сложность вашего алгоритма, так сразу можете получить и грубую оценку того, как быстро он будет работать, приняв, что в секунду выполняется 1 000 000 команд. Их количество считается из полученной вами функции асимптотической оценки, описывающей алгоритм. Например, вычисление по алгоритму с Θ( n ) займёт около секунды при n = 1 000 000.

То есть мой процессор делает мильён сферических атомарных операций (которые там названы инструкциями, что-то вроде mov, наверно) в вакууме. Супер.

То есть мой процессор делает мильён сферических атомарных операций (которые там названы инструкциями, что-то вроде mov, наверно) в вакууме. Супер.

вот тебе смешно, а кому-то с такими работать приходится... Да, с «медленно растущим логарифмом», и с «большой фитой».

Это замечательно, что ты знаешь свойства логарифма. Я тоже тобой горжусь.

Это замечательно, что ты знаешь свойства логарифма. Я тоже тобой горжусь.

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

Т.ч. гордится тут нечему.

Я считаю принципиально неправильным подавать материал с ошибками.

Ладно, соглашусь, стоило бы там сделать пометку типа «для нашего случая», или поместить графики после слов о том, что мы рассматриваем двоичный логарифм, и говорить конкретно о нём.

Т.ч. гордится тут нечему.

Но ведь хочется. Иначе зачем ты это всё писал?

P.S. Про отличия О-большого от Θ там написано в тексте.

Но ведь хочется. Иначе зачем ты это всё писал?

в интернетах опять кто-то неправ.

P.S. Про отличия О-большого от Θ там написано в тексте.

чушь там написана полная.

кому интересно, вот что такое «большая тета»: http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau...

Я вот только не понял — кому это нафиг вообще надо-то?

Ты быдло.

Модераторы! Обратите внимание на сраную политоту в аватарке!

Логарифм — это операция, которая при применении её к числу делает его гораздо меньше
Сколько будет логарифм 1/4 по основанию 1/2?

А это смотря как считать больше-меньше. Если по количеству бит, то на запись числа 2 хватит двух бит в обычном представлении, а вот для чисел с плавающей точкой редко используется менее 16 (half precision).

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

2

Я вот только не понял — кому это нафиг вообще надо-то?

Это отношение эквивалентности, оно требуется любому образованному в области теории алгоритмов человеку.

Вангую скрытую лемму о том, что «логарифм» — это «натуральный логарифм».

забавно , что школьное образование втыкает в головы модули , а не целостные мировозрения

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

кста из того же русла задачка взять производную и построить график функции y = x в степени x

видимо они под числом называют number ( т.е натуральное) - для которого его логарифм по натуральному будет меньше .

Видимо они решили не умничать там где этого не требуется :)

что??????????????

логорифмы же знакомят(чисто ознакомительно) со школотой и наоборот в том же классе когда расказывают правила работы со степенями - как они складываются вычетаются умножаются тут экскурс в корни и делятся - и тут же чисто из за того что все 3 аргумента в равенстве играют отличную друг от друга роль ( в отличии от сложения и умножения которые перестановочны И вычитания и деления которые обратны )

т.е степень( как спецефичное обобщение умножения) - корень ( как обратность степени) и логарифм ( как «обратность» степени по другому аргументу, и как «обратность» корню) - в одном классе 5-6 узнают в правильных школах .

конечно кучу правил и прочего матана можно и в 10 классе логарифмировать

но разносить по времени возведение в степень корнение и логарифмирования это шизофреничная практика

чего?

В 10-м классе будете проходить.

что??????????????

Явно неадекватная реакция.

ибо нужны были :

танкисты

артелеристы

и прочии летуны

у которых «sin(x) в военное время может достигать и 5и»

зачем логарифмы отрывают/оторвали от степени и корня?

помню нам ( в обычной школе) обьяснили принцып работы логарифмической линейки как раз в 5 классе - т.е. первый класс средней ступени средней школы .

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

Это отношение эквивалентности, оно требуется любому образованному в области теории алгоритмов человеку.

хвастаться? Ну давай, рассказывай. ЗАЧЕМ оно тебе?

Чтобы алгоритмы исследовать, внезапно.

пример-то будет? какой алгоритм посл. исследовал?

А посоветуйте алгоритм/структуру данных для быстрейшего поиска точки (точек) в порядке удалённости от заданной в 2D?

Ну им надо было объяснить для нубов про натуральные логарифмы. Они выделили суть, не вдаваясь в подробности. Правильно же.

для обьяснения нубам логарифмов достаточно

основание в степени == результат

(по основанию ) в степени (логарифм по основанию от результата) == результат

Линейка это вещь! Если надо считать с точностью до двух-трех цифр, то куда быстрее и удобнее любого калькулятора. Но сейчас же учат не думать а кнопки давить...

Кстати, кто занимается разработкой под всякие смартфоны, дарб идею - калькулятор оформленный под логарифмическую линейку. С мультитачами и драг-энд-дропами это должно быть здорово удобно.