Alexandroppolus, Как именно придуманные вами случаи и усложнения относятся к вопросу, который задан автором? У автора (и у меня в ответе) под поиском понимается поиск хвоста списка, который ищется за O(n).
И непонятно, с чего вдруг это должно разваливать теорию оценок.
Потому что вся теория того, как работает поиск, (и не только в массиве, а например, в карте) дается для случая, что предикат проверяется за O(1). Для более сложного предиката теорию нужно будет разрабатывать заново, потому что O(N * f(N)) - это некое новшество, которое непонятно как оценивать.
ну так проверка элемента вполне может включать в себя работу с тем же массивом. O(1) на элемент - это частный случай.
Откройте уже для себя учебник Кнута про сортировку и поиск и разберитесь, что называется поиском элемента в массиве. Под проверкой элемента там понимается вполне конкретная операция со сложностью O(1), в противном случае, вся постороенная теория оценок сложности алгоритмов развалится.
то частный случай. И в вопросе пользователя такого не было.
если внимательно прочитать вопрос, он весь сделан в предположении, что вставка происходит в конец контейнера. Что является наихудшим случаем для связного списка (если мы не храним указатель на хвост), и почти всегда является наилучшим случаем для массива {отсюда и недоумение, почему вставка в массив занимает так много - при вставке в хвост массива обычно достаточно просто впихнуть элемент, а про случай исчерпания памяти автор вопроса не подумал}
Собственно, их этого предположения и развилось дальнейшее непонимание и возник этот пост.
Alexandroppolus, это уже не задача поиска в массиве (У которой есть вполне конкретное определение - нужно перебирать элементы и для каждого делать проверку), а ваше изобретение, притянутое за уши в поддержку вашей версии.
В реальности же есть операция преобразования индекса в указатель. Для массивов это делается за O(1), для списков за O(n).
Ключевым для автора вопроса является то, что автор книги посчитал время вставки в список как O(1) исходя из предположения, что указатель уже есть в распоряжении программиста. Если же у программиста есть только индекс элемента (что на практике встречается довольно часто), к сложности добавляется вполне конкретный процесс поиска указателя на элемент с нужным индексом, который делается за O(n)
Вы же зачем-то к сложности конкретной операции вставки пытаетесь притянуть часть прикладного алгоритма, что методологически неверно.
-популярность книги не всегда означает высокое качество. Например, она понравилась какой-то пачке профессионалов (по тому что для них она является беллетристикой и приятным чтением, а алгоритмы они изучали в другом месте), которые начали ее советовать на всех углах.
-то что автору не удалось что-то объяснить лично вам не означает, что автор плохой для всех читателей - он плохой персонально для вас (строго говоря, для такого утверждения нужно накопить историю взаимного непонимания). К счастью, на свете есть другие авторы.
Профессионалы обычно являются плохими (если не сказать больше) учителями (ровно как и учителя являются плохими профессионалами), потому что эти люди занимаются разной деятельностью и имеют разные цели.
Как минимум, профессионал использует все свои знания в комплексе, а учитель скован педагогическим процессом и должен выдавать знания дозированно - иначе ученик треснет (что с вами и произошло в данном случае)
res2001, оно обоснованно, когда книжку читает программист со стажем, который в состоянии понять, откуда ветер дует и что творится в голове у автора. (С другой стороны, нафига ему тогда книжка, разве что в качестве беллетристики).
Неопытный же читатель оказывается в рекурсивном тупике - чтобы понять книгу по алгоритмам, нужно понимать алгоритмы. Выходом было бы аккуратное объяснение что к чему с явным указанием мотивов автора.
ivan58, если честно, я очень сомневаюсь в своем объяснении ситуации. Наверняка диффпара цепляется к какой-то искуственной земле через какие-то компоненты, потому что на обратном токе коллектора далеко не уедешь.
Более того, я считаю малопродуктивной вашу затею изучения интерфейсов путем залезания на уровень отдельных транзисторов - для реальной практики в цифровой электронике, достаточно работы на уровне чипов и повторения схем из даташитов. Вы же тратите время на выяснение того, какой там транзистор куда открылся.
Виктор, так это и есть постоянный ток, я же написал, по какому пути он пойдет ( Б-Э левого транзистора, R3, источник ЭДС питания усилителя, R2, К-Б правого транзистора, источник ЭДС, питающий диффапару)
Виктор, я же написал, как ЭДС источника сигнала будет таскать электроны с эммитера на базу одного из транзисторов, что является необходимым условием его открытия, которое приведет к перекосу схемы и появлению разности потенциалов на выходах A и B
Напоминаю, что помимо встречно закрытых эммитерных переходов в схеме дифкаскада обязательно есть источник тока, который очень хочет вкачивать электроны в точку соединения эмитеров
ivan58, Попробуйте ноутбук из розетки выключить - тогда вы убедитесь, что дифференциальной паре третий провод не нужен. Достаточно, чтобы между базами транзисторов была приложена ЭДС
В ваших схемах не нарисована важная штука - питание дифференциальной пары источником стабильного тока, которое и обеспечивает реакцию дифференциального усилителя на появление разности потенциалов между базами.
Рассмотрите это так. Из базы левого транзистора ЭДС передатчика украла электон, Через переход ЭБ на его место затянулся другой электрон. Источник тока, питающий схему, обязан поддерживать стабильный ток, поэтому он утянул электрон из той точки, куда подключены коллекторы обоих транзисторов.
В это же время ЭДС передатчика занята тем, что пытается впихнуть сворованный у левого транзистора электрон в базу правого, а на коллекторе у него же как раз есть децифит в один электрон, созданный источником питания усилителя. переход КБ в эту сторону - открыт, так что ток прекрасно себе начинает протекать по схеме.
Этот ток заставляет левый транзистор открыться, перекашивая напряжения на выходах усилителя. Ура-ура, все работает без привязки передатчика к земле.
Чтобы совсем убедиться в этом, засуньте схему в он-лайн эмулятор (что я только что и сделал)
Черное на графике - сигнал с генератора, который подключен к базам транзисторов.
Синее - то, что выходит из усилителя ( в дифференциальной форме)
ivan58, чем ближе свиты провода, тем одинаковее в них будет наводка, которая потом будет вычитаться. Чем вы руководствовались, объединяя провода таким образом?