DB>Естественно нет. Никогда и нигде задачи в виде "подсчитай алгоритмическую сложность этого куска кода" не было.

Как не было. Сходите в гугл на собеседование, это там в каждой задаче.

KP>Подсчитать — нет. Подумать какой из алгоритмов/контейнеров будет оптимальным в данный момент или придумать как решить ту или иную алгоритмическую задачу — очень часто. И вот для этого "очень часто" знание, хотя бы приблизительное, того, как устроены контейнеры, или какова сложноть у алоритмов необходимо. Хотя, возможно, это потому, что я вообще не занимаюсь ни бухгалтерией, ни документоообротом.

Посыл верный (что иногда требуется выбрать структуру данных), но вывод неверный (про необходимость знать внутреннее устройство контейнера или про сложность конкретного алгоритма).
Потому как достаточно просто взять табличку с перечислением оных контейнеров али алгоритмов — и на ее основании выбрать нужный. Предположим, программист не знает, какой асимптотической сложностью обладает LinkedList, но ему нужен контейнер, в который часто проводятся вставки и удаления, по которому часто итерируются, но произвольный индексный доступ не требуется. По табличке прошелся, выбрал нужный — пошел дальше.

Индусы так работают. Работают успешно — в том смысле, что продукты выпускаются, бизнесу выгодно.

Здравствуйте, B0FEE664, Вы писали:

BFE>Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность. Вот, например, кто-нибудь рассуждает так: "Окно в первом прототипе будет обрабатывать 5 сообщений. Количество сообщений по мере развития приложения может увеличится до сотни. Если мы напишем switch(номер сообщения), то алгоритмическая сложность составит O(n). Но ведь есть алгоритм бинарного поиска! Его алгоритмическая сложность меньше. Что-ж, заведём массив хранящий пару (номер сообщения, обработчик), отсортируем его по номеру сообщения и будем применять бинарный поиск! Тааак... теперь надо выбрать правильный алгоритм сортировки..."

Ага. Видел таких гениев, что за деревьями не видят леса. Убъют две трети времени проекта на оптимизацию того, что в итоге либо не окажет никакого влияния на производительность, а то и будет вообще выкинуто, и прохлопают очевиднейшее бутылочное горлышко, в котором наговнокодят даже не O(n^2), а O(n^n). Специалисты блин, и все как один с дипломами, гномиков с закрытыми глазами считают и сортировки пальцами левой ноги на бумажке пишут.

М>да-да. хэш таблицы. поиск по словам post hashmap dos рулит. очень интересная дыра. потому что никому и в голову не пришло просчитать наихудший сценарий развития событий.

ну я минимум 10 лет назад понимал возможность таких DoS

MTD>Нет. Компилятор для свича построит таблицу переходов и вуаля — О(1)

Что-то вас занесло. Немало современных кодогенераторов довольно тупо поступает — генерирует пары test reg, const -> jz caseconst.

ПМ> было бы интересно взглянуть на компилятор, который сам конвертирует свитчи в двоичный поиск, потому что что-то я сомневаюсь в целесообразности такой операции.

gcc при определенных ключах компиляции

L>Ага. Видел таких гениев, что за деревьями не видят леса. Убъют две трети времени проекта на оптимизацию того, что в итоге либо не окажет никакого влияния на производительность, а то и будет вообще выкинуто, и прохлопают очевиднейшее бутылочное горлышко, в котором наговнокодят даже не O(n^2), а O(n^n). Специалисты блин, и все как один с дипломами, гномиков с закрытыми глазами считают и сортировки пальцами левой ноги на бумажке пишут.

Но ведь это же хорошо! Для нас с тобой, как минимум

Здравствуйте, SkyDance, Вы писали:

L>>Ага. Видел таких гениев, что за деревьями не видят леса. Убъют две трети времени проекта на оптимизацию того, что в итоге либо не окажет никакого влияния на производительность, а то и будет вообще выкинуто, и прохлопают очевиднейшее бутылочное горлышко, в котором наговнокодят даже не O(n^2), а O(n^n). Специалисты блин, и все как один с дипломами, гномиков с закрытыми глазами считают и сортировки пальцами левой ноги на бумажке пишут.

SD>Но ведь это же хорошо! Для нас с тобой, как минимум

Да как-то задалбывает бороться с ветряными мельницами, если честно.

Здравствуйте, _DAle_, Вы писали:

_DA>Не надо шокироваться. List — это просто упорядоченный набор элементов. И у него обычно две реализации: array и linked list. В терминологии на русском языке часто под словом "список" подразумевается linked list из-за этого и часто возникающая путаница.

Лучше уж тогда избегать путающих вопросов.

L>Да как-то задалбывает бороться с ветряными мельницами, если честно.

Do not fight it. Embrace it! (C)

Здравствуйте, SkyDance, Вы писали:

L>>Да как-то задалбывает бороться с ветряными мельницами, если честно.

SD>Do not fight it. Embrace it! (C)

Так тоже можно. Жаль только, что эти Выбегаллы сильно портят имидж профессии.

Здравствуйте, B0FEE664, Вы писали:

MTD>>Количество шагов может быть небольшим, а время выполнения огромным по сравнению с поставленными временными рамками. Так что это важно.
BFE>Нет. Это значит, что для разных задач нужны разные алгоритмы.

Молодец, мозг включился

BFE>если никаких проблем, значит и цикл можно развернуть по тому же принципу.

Можно в некоторых случаях.

BFE>А причем тут цикл обработки 100 гигабитного потока?

А при чем тут лист бокс?

SD>>Do not fight it. Embrace it! (C)
L>Так тоже можно. Жаль только, что эти Выбегаллы сильно портят имидж профессии.

Что, простите, портят?
Имидж, простите, профессии _ПРОГРАММИСТА_?!

Не, я еще понимаю, ореол таинственности и мифичности, но чтоб "имидж".
Имид — это, вот, скажем, в России — работа сантехника.
Или, например, в США — юриста. Это имидж. А программист...

Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, MTD, Вы писали:

BFE>>>И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?
MTD>>Ну вот как, как, такое может придти в голову?
BFE>Как, как ... Из практики!

MTD>> Я даже не об алгоритмах говорю, а о несчастных юзерах.

BFE>Что с ними не так? Их последнее время расплодилось столько, что в 32 бита не влезают.

Да уж... Может чем нибудь другим стоит заняться?

MTD>> Однозначно теперь первый вопрос про О-большое, ну после виртуального деструктора

BFE>Ну причём тут О-большое

Сразу позволяет понять стоит общаться дальше или нет. После этой темы я это хорошо понял.

Здравствуйте, MescalitoPeyot, Вы писали:

MP>Здравствуйте, Злобастик, Вы писали:

З>>Я вообще никогда в жизни не слышал о таком понятии, как "алгоритмическая сложность". Нигде — ни в институте, ни на работе, ни в книжках, ни в интернетах, ни от коллег.

MP>Еще скажите, что на матане вы O-нотацию не проходили.

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

Здравствуйте, Паблик Морозов, Вы писали:

ПМ>Здравствуйте, Sorc17, Вы писали:

S>>"Спасибо, мы вам перезвоним в ближайшее время?"

ПМ>Я не устраиваю собеседований в онлайне на rsdn, но когда мне так отвечают, я интересуюсь, как именно устроен ArrayList. В 100% случаев не отвечают. Дальше, как правило, следует еще пяток неверных ответов по основам используемой платформы, пяток неверных ответов по поводу специфичных вещей, нужных для проекта и, как правило, "спасибо, мы вам перезвоним в ближайшее время". Поэтому я и говорю, что всякие вычислительные сложности — это индикаторы. Если по ним незачёт, то дальше можно не продолжать, с высокой вероятностью ничего не потеряете, но сэкономите время.

А, там таки массив внутри. http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html А я в своё время по диагонали прочитал, видимо Щито поделать.

Всё же при switch будет N сравнений, где N это количество кейсов. Пруф:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
int main (int argc, char* argv[]) {
    int a = atoi(argv[1]);
    switch (a) {
        case 2:
            printf("2");
            break;
        case 5:
            printf("5");
            break;
        default:
            printf("Unexpected");
            break;
    }
    return EXIT_SUCCESS;
}

$ gcc -S -O3 1.c -o 1.s
$ cat 1.s
    .file    "1.c"
    .section    .rodata.str1.1,"aMS",@progbits,1
.LC0:
    .string    "Unexpected"
    .section    .text.startup,"ax",@progbits
    .p2align 4,,15
    .globl    main
    .type    main, @function
main:
.LFB30:
    .cfi_startproc
    subq    $8, %rsp
    .cfi_def_cfa_offset 16
    movq    8(%rsi), %rdi
    movl    $10, %edx
    xorl    %esi, %esi
    call    strtol
    cmpl    $2, %eax
    je    .L3
    cmpl    $5, %eax
    je    .L8
    movl    $.LC0, %edi
    xorl    %eax, %eax
    call    printf
.L5:
    xorl    %eax, %eax
    addq    $8, %rsp
    .cfi_remember_state
    .cfi_def_cfa_offset 8
    ret
.L3:
    .cfi_restore_state
    movl    $50, %edi
    call    putchar
    jmp    .L5
.L8:
    movl    $53, %edi
    call    putchar
    .p2align 4,,3
    jmp    .L5
    .cfi_endproc
.LFE30:
    .size    main, .-main
    .ident    "GCC: (GNU) 4.6.1 20110908 (Red Hat 4.6.1-9)"
    .section    .note.GNU-stack,"",@progbits
$

S>Всё же при switch будет N сравнений, где N это количество кейсов. Пруф:

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

Здравствуйте, мыщъх, Вы писали:

MTD>>>... или что проход по массиву n элементов имеет сложность O(n) ?!!
S>>Зачем это знать? Написал foreach и всё. Какая разница какая там у него сложность?
М>ну как бы последняя крупная дос дыра как раз и связана с тем, что для передачи аргументов web-программисты используют hashmap без понимания как оно работает и пацаны придумали как валить мощные сервера даже со слабого модема на 33,600. если в худшем случае у нас квадратичная сложность, то это означает, что покупкой оборудования проблему не исправить.

Если бы кто эти сервера валил. На каждый второй заходишь и он минуту думает, что показать. Навигация по сайту превращается в муку — стоит ли тратить своё время, чтобы узнать что есть на этом сайте, или лучше посмотреть сайты конкурентов? И почти на каждом сайте вначале будет тупое видео, хорошо, если звук не на полную громкость выставлен.

Здравствуйте, vpchelko, Вы писали:

_DA>>Не надо шокироваться. List — это просто упорядоченный набор элементов. И у него обычно две реализации: array и linked list. В терминологии на русском языке часто под словом "список" подразумевается linked list из-за этого и часто возникающая путаница.

V>Лучше уж тогда избегать путающих вопросов.

Там цель отсеять, поэтому он такие вопросы специально накапливает.