Временная сложность преобразования некоторых элементов 2d массива в 1d массив

Я пытаюсь реализовать Radix Sort по-своему. Я успешно реализовал это, но у меня есть сомнения, что я мог изменить временную сложность сортировки моим методом. поэтому предположим, что у меня есть массив 1 d с 7 элементами, которые я хочу отсортировать. Я сделал 2d массив размером 7X10 (который будет использоваться как корзина), так что этот 2d будет иметь максимум 7 ненулевых элементов, а остальные будут равны нулю. Теперь в моей реализации наступает шаг, на котором я должен скопировать эти ненулевые элементы из 2d-массива в мой исходный 1d-массив, поэтому я пишу его код следующим образом

Примечание: c - это индексная переменная, инициализированная 0 и увеличивающаяся

for(int i=0;i<10;i++)
          {
              for(int j=0;j<bkt.length;j++)
              {
                  if(bkt[j][i]!=0)
                  {
                      ar[c]=bkt[j][i];
                      c++;
                  }
              }
          }

так что эти вложенные циклы меняют сложность моего времени? сложность времени будет зависеть от того, сколько раз условие будет выполнено?

или позвольте мне упростить вопрос, предположим, что у меня есть двумерный массив nXn, и он имеет 10 ненулевых элементов, а остаток равен 0, и предположим, что я применяю аналогичный шаг для копирования ненулевых элементов массива в одномерный массив. будет ли временная сложность этого шага равна n^2, так как есть 2 для циклов, а значения i и j увеличиваются только на 1, поэтому все элементы необходимо сканировать??

0 ответов

Другие вопросы по тегам