LEVEL: Циклы while, foreach, goto, повторяющие for

HJSON

{
  name: While & Foreach
  description: Описание: Задачи на разные алгоритмы и разные сложности
  levels:
  [
    {
      next_levels:
      [

      ]
      description: Циклы while, foreach 
      number: 0
      generators:
      [
        {
          possible_answers:
          [
            Θ(log({{to1}}))
            Θ(√{{to1}})
            Θ(1)
            Θ({{to1}})
            Θ({{to1}}²)
          ]
          text:
            '''
            var {{loop_var1}} = 0;
            while({{loop_var1}} < {{to1}})
            {
              var {{loop_var2}} = 0;
              while({{loop_var2}} < {{to1}})
                {{loop_var2}}++;
              {{loop_var1}}++;
            }
            '''
          question: Оцени временную сложность данного алгоритма:
          hints: 
          [
            ∀ {{loop_var1}}: {{loop_var2}} проходит от 0 до {{to1}}
          ]
          answer: Θ({{to1}}²)
          streak: 2
        }
        {
          possible_answers:
          [
            Θ(log({{to1}}))
            Θ(√{{to1}})
            Θ(1)
            Θ({{to1}})
            Θ({{to1}}²)
          ]
          text:
            '''            
            var {{loop_var1}} = 0;
            while({{loop_var1}} < {{to1}})
            {
              var {{loop_var2}} = {{loop_var1}};
              while({{loop_var2}} < {{to1}} && {{loop_var2}} < {{loop_var1}} + {{from1}})       
                {{loop_var2}}++;
              {{loop_var1}} = {{loop_var2}};
            }
            '''
          question: Оцени временную сложность данного алгоритма:
          hints: 
          [
          ]
          answer: Θ({{to1}})
          streak: 1
        }
        {
          possible_answers:
          [
            Θ(log({{to1}}))
            Θ(√{{to1}})
            Θ(1)
            Θ({{to1}})
            Θ({{to1}}²)
          ]
          text:
            '''     
            var {{loop_var1}} = 0;
            while({{loop_var1}} < {{to1}})
            {
              {{loop_var2}} = {{loop_var1}};
              while({{loop_var2}} < {{to1}} && {{loop_var2}} < {{loop_var1}} + {{from1}})       
                {{loop_var2}}++;
              {{loop_var1}} = {{loop_var2}};
            }
            '''
          question: Оцени временную сложность данного алгоритма:
          hints: 
          [
          ]
          answer: Θ({{to1}})
          streak: 2
        }
        {
          possible_answers:
          [
            Θ(log({{to1}}))
            Θ(√{{to1}})
            Θ(1)
            Θ({{to1}})
            Θ({{to1}}²)
          ]
          text:
            '''
            var array = new int[{{to1}}]{...}; // {{to1}} элементов  
            var minIndex = 0;
            var maxIndex = array.Length - 1;
            while (minIndex <= maxIndex) 
            {
                var currentIndex = (minIndex + maxIndex) / 2;
                var currentElement = array[currentIndex];
                if (currentElement < targetValue) 
                  minIndex = currentIndex + 1;
                else if (currentElement > targetValue) 
                  maxIndex = currentIndex - 1;
                else 
                  return currentIndex;
            }
            '''
          question: Оцени временную сложность данного алгоритма:
          hints: 
          [
            Вспомни сложность бинарного поиска
          ]
          answer: Θ(log({{to1}}))
          streak: 2
        }
        {
          possible_answers:
          [
            Θ(log({{to1}}))
            Θ(√{{to1}})
            Θ(1)
            Θ({{to1}})
            Θ({{to1}}²)
          ]
          text:
            '''
            var c = 0;
            var words = new string[{{to1}}] {...} // {{to1}} слов, длины const
            foreach(var word in words):
              foreach(var letter in word):
                  if (letter == 'a'):
                    c++;
            '''
          question: Оцени временную сложность данного алгоритма:
          hints: 
          [
            Θ(const * N), где N - размер массива
          ]
          answer: Θ({{to1}})
          streak: 2
        }
      
        {
          possible_answers:
          [
            Θ({{to1}} {{multiply}} log({{to1}}))
            Θ({{to1}})
            Θ({{to1}}³)
            Θ({{to1}}² {{multiply}} log({{to1}}))
            Θ({{to1}}²)
          ]
          text:
            '''
            var list = new List<int>();
            var {{loop_var1}} = 0;
            var {{loop_var2}} = 0;
            while({{loop_var1}} < {{to1}})
            {
              while({{loop_var2}} < {{loop_var1}})
              {
                list.Add({{loop_var1}} * {{loop_var2}}); // ← аморт. оценка Θ(1)
                {{loop_var2}}++;
              }
              {{loop_var1}}++;
              {{loop_var2}} = 0;
            }
            '''
          question: Оцени временную сложность данного алгоритма:
          hints: 
          [
            Обрати внимание, сколько раз выполнится list.Add
          ]
          answer: Θ({{to1}}²)
          streak: 2
        }
      ]
    }
  ]
}