LEVEL: Двойные независимые циклы

Сложность

Данный уровень является средним по сложности и идет вторым в списке, после одинарных циклов

Задания

Двойные циклы, при этом внутренний не использует переменную внешнего (независимые).
Каждый из них зависит от одной и той же переменной

Один из циклов всегда стандартный (с точностью до названий переменных и констант):
for (var i = 0; i < n; i++)

А у второго возможны 4 случая:

• for (var j = 0; j < n; j++)
• for (var j = 0; j < n; j *= 2)
• for (var j = 0; j < n * n; j++)
• for (var j = 0; j * j < n; j++)

Все генераторы используют комбинацию этих циклов (7 вариантов)

Ответы

Возможны 4 варианта ответа:

• Θ(n ∙ log(n))
• Θ(n ∙ √n)
• Θ(n²)
• Θ(n³)

Так же добавлен вариант ответа Θ(n) для запутывания пользователей

Подсказки

Первый генератор (самый простой) имеет лишь 2 подсказки:

• Попробуй посчитать количество независимых операций
• Обрати внимание на то, что циклы независимы

Все остальные, также имеют 1 дополнительную, указывающую, какой из циклов сложнее:

• Внимательно изучи [внутренний | внешний] цикл

И еще 1 индивидуальную:

• Посмотри как изменяется переменная цикла на каждой итерации
• Посмотри на верхнюю границу цикла
• Посмотри на условие выхода из цикла

Прогресс

Задания каждого генератора нужно решить 2 раза, таким образом общее количество заданий в уровне равно 14

Код

Ниже представлен код уровней в формате HJSON

{
    name: Artemiy's test
    description: Тестовая тема для двойных независимых циклов
    levels:
    [
        {
            next_levels:
            [

            ]
            description: Двойные независимые циклы
            number: 0
            generators:
            [
                {
                    question: Оцени временную сложность данного алгоритма:
                    text: 
                        '''
                        for (var {{loop_var1}} = {{from1}}; {{loop_var1}} < {{to1}}; {{loop_var1}} += {{iter1}})
                            for (var {{loop_var2}} = {{from2}}; {{loop_var2}} < {{to1}}; {{loop_var2}} += {{iter2}})
                                {{simple_operation1}}
                        '''
                    answer: '{{theta}}({{to1}}{{pow2}})'
                    possible_answers:
                    [
                        '{{theta}}({{to1}})'
                        '{{theta}}({{to1}} {{multiply}} {{sqrt}}{{to1}})'
                        '{{theta}}({{to1}} {{multiply}} log({{to1}}))'
                        '{{theta}}({{to1}}{{pow2}})'
                        '{{theta}}({{to1}}{{pow3}})'
                    ]
                    hints:
                    [
                        Попробуй посчитать количество независимых операций
                        Обрати внимание на то, что циклы независимы
                    ]
                    streak: 2
                }
                {
                    question: Оцени временную сложность данного алгоритма:
                    text: 
                        '''
                        for (var {{loop_var1}} = {{from1}}; {{loop_var1}} < {{to1}}; {{loop_var1}} += {{iter1}})
                            for (var {{loop_var2}} = {{from2}}; {{loop_var2}} < {{to1}}; {{loop_var2}} *= {{iter2}})
                                {{simple_operation1}}
                        '''
                    answer: '{{theta}}({{to1}} {{multiply}} log({{to1}}))'
                    possible_answers:
                    [
                        '{{theta}}({{to1}})'
                        '{{theta}}({{to1}} {{multiply}} {{sqrt}}{{to1}})'
                        '{{theta}}({{to1}} {{multiply}} log({{to1}}))'
                        '{{theta}}({{to1}}{{pow2}})'
                        '{{theta}}({{to1}}{{pow3}})'
                    ]
                    hints:
                    [
                        Попробуй посчитать количество независимых операций
                        Обрати внимание на то, что циклы независимы
                        Внимательно изучи внутренний цикл
                        Посмотри как изменяется переменная цикла на каждой итерации
                    ]
                    streak: 2
                }
                {
                    question: Оцени временную сложность данного алгоритма:
                    text: 
                        '''
                        for (var {{loop_var1}} = {{from1}}; {{loop_var1}} < {{to1}}; {{loop_var1}} *= {{iter1}})
                            for (var {{loop_var2}} = {{from2}}; {{loop_var2}} < {{to1}}; {{loop_var2}} += {{iter2}})
                                {{simple_operation1}}
                        '''
                    answer: '{{theta}}({{to1}} {{multiply}} log({{to1}}))'
                    possible_answers:
                    [
                        '{{theta}}({{to1}})'
                        '{{theta}}({{to1}} {{multiply}} {{sqrt}}{{to1}})'
                        '{{theta}}({{to1}} {{multiply}} log({{to1}}))'
                        '{{theta}}({{to1}}{{pow2}})'
                        '{{theta}}({{to1}}{{pow3}})'
                    ]
                    hints:
                    [
                        Попробуй посчитать количество независимых операций
                        Обрати внимание на то, что циклы независимы
                        Внимательно изучи внешний цикл
                        Посмотри как изменяется переменная цикла на каждой итерации
                    ]
                    streak: 2
                }
                {
                    question: Оцени временную сложность данного алгоритма:
                    text: 
                        '''
                        for (var {{loop_var1}} = {{from1}}; {{loop_var1}} < {{to1}} * {{to1}}; {{loop_var1}} += {{iter1}})
                            for (var {{loop_var2}} = {{from2}}; {{loop_var2}} < {{to1}}; {{loop_var2}} += {{iter2}})
                                {{simple_operation1}}
                        '''
                    answer: '{{theta}}({{to1}}{{pow3}})'
                    possible_answers:
                    [
                        '{{theta}}({{to1}})'
                        '{{theta}}({{to1}} {{multiply}} {{sqrt}}{{to1}})'
                        '{{theta}}({{to1}} {{multiply}} log({{to1}}))'
                        '{{theta}}({{to1}}{{pow2}})'
                        '{{theta}}({{to1}}{{pow3}})'
                    ]
                    hints:
                    [
                        Попробуй посчитать количество независимых операций
                        Обрати внимание на то, что циклы независимы
                        Внимательно изучи внешний цикл
                        Посмотри на верхнюю границу цикла
                    ]
                    streak: 2
                }
                {
                    question: Оцени временную сложность данного алгоритма:
                    text: 
                        '''
                        for (var {{loop_var1}} = {{from1}}; {{loop_var1}} < {{to1}}; {{loop_var1}} += {{iter1}})
                            for (var {{loop_var2}} = {{from2}}; {{loop_var2}} < {{to1}} * {{to1}}; {{loop_var2}} += {{iter2}})
                                {{simple_operation1}}
                        '''
                    answer: '{{theta}}({{to1}}{{pow3}})'
                    possible_answers:
                    [
                        '{{theta}}({{to1}})'
                        '{{theta}}({{to1}} {{multiply}} {{sqrt}}{{to1}})'
                        '{{theta}}({{to1}} {{multiply}} log({{to1}}))'
                        '{{theta}}({{to1}}{{pow2}})'
                        '{{theta}}({{to1}}{{pow3}})'
                    ]
                    hints:
                    [
                        Попробуй посчитать количество независимых операций
                        Обрати внимание на то, что циклы независимы
                        Внимательно изучи внутренний цикл
                        Посмотри на верхнюю границу цикла
                    ]
                    streak: 2
                }
                {
                    question: Оцени временную сложность данного алгоритма:
                    text: 
                        '''
                        for (var {{loop_var1}} = {{from1}}; {{loop_var1}} < {{to1}}; {{loop_var1}} += {{iter1}})
                            for (var {{loop_var2}} = {{from2}}; {{loop_var2}} * {{loop_var2}} < {{to1}}; {{loop_var2}} += {{iter2}})
                                {{simple_operation1}}
                        '''
                    answer: '{{theta}}({{to1}} {{multiply}} {{sqrt}}{{to1}})'
                    possible_answers:
                    [
                        '{{theta}}({{to1}})'
                        '{{theta}}({{to1}} {{multiply}} {{sqrt}}{{to1}})'
                        '{{theta}}({{to1}} {{multiply}} log({{to1}}))'
                        '{{theta}}({{to1}}{{pow2}})'
                        '{{theta}}({{to1}}{{pow3}})'
                    ]
                    hints:
                    [
                        Попробуй посчитать количество независимых операций
                        Обрати внимание на то, что циклы независимы
                        Внимательно изучи внутренний цикл
                        Посмотри на условие выхода из цикла
                    ]
                    streak: 2
                }
                {
                    question: Оцени временную сложность данного алгоритма:
                    text: 
                        '''
                        for (var {{loop_var1}} = {{from1}}; {{loop_var1}} * {{loop_var1}} < {{to1}}; {{loop_var1}} += {{iter1}})
                            for (var {{loop_var2}} = {{from2}}; {{loop_var2}} < {{to1}}; {{loop_var2}} += {{iter2}})
                                {{simple_operation1}}
                        '''
                    answer: '{{theta}}({{to1}} {{multiply}} {{sqrt}}{{to1}})'
                    possible_answers:
                    [
                        '{{theta}}({{to1}})'
                        '{{theta}}({{to1}} {{multiply}} {{sqrt}}{{to1}})'
                        '{{theta}}({{to1}} {{multiply}} log({{to1}}))'
                        '{{theta}}({{to1}}{{pow2}})'
                        '{{theta}}({{to1}}{{pow3}})'
                    ]
                    hints:
                    [
                        Попробуй посчитать количество независимых операций
                        Обрати внимание на то, что циклы независимы
                        Внимательно изучи внешний цикл
                        Посмотри на условие выхода из цикла
                    ]
                    streak: 2
                }
            ]
        }
    ]
}