Analyze complexity of algorithm
Please describe your question in more details.
Я думаю, человек имеет в виду, почему когда у нас есть цикл от 1 до n, мы не учитываем количество сравнений (на каждом шаге цикла мы должны сравнивать переменную цикла с верхней или нижней границей) при анализе сложности алгоритма.
Мое мнение, что во-первых, здесь очень простые сравнение, а сравнения элементов структур алгоритма могут быть намного затратнее.
А во-вторых, такие циклы могут быть организованы или развернуты компилятором в ассемблерные конструкции loop и их аналоги, которые явно не используют сравнения.
Как мой ответ перевести на английский не знаю. Если кто-то согласен с моим пониманием вопроса и моими ответами на него, и хорошо знает английский, переведите пожалуйста.
Мое мнение, что во-первых, здесь очень простые сравнение, а сравнения элементов структур алгоритма могут быть намного затратнее.
А во-вторых, такие циклы могут быть организованы или развернуты компилятором в ассемблерные конструкции loop и их аналоги, которые явно не используют сравнения.
Как мой ответ перевести на английский не знаю. Если кто-то согласен с моим пониманием вопроса и моими ответами на него, и хорошо знает английский, переведите пожалуйста.
why do not need to count comparision of loop for ("for i:=1 to n", n+1 comparisions)?We should count it, but usually it only increases the constant of big-O. Thus, empty loop, if not optimized, will have O(N) complexity.
Оставить комментарий
Lynx
why do not need to count comparision of loop for ("for i:=1 to n", n+1 comparisions)?