Правильно ли я понял сложность времени? - PullRequest
Новая
       10

Правильно ли я понял сложность времени?

0 голосов
/ 01 января 2019

Для следующей задачи я предоставил алгоритм;однако я не уверен, является ли вычисленная сложность правильной или нет.Я запутался в подсчете сложности цикла while из-за того, что понятия не имею, сколько раз он будет выполняться.

проблема:

Выбор k-элементов из списка из n различных целых чисел случайным образом и без повторений (т.е. элемент не должен выбираться более одного раза).Предположим, вам дана функция random (m), которая случайным образом выбирает целое число от 1 до m.

Мой алгоритм + сложности: 

int count = k;                          O(1)
int list[] = new list[k];               O(1)
for(int i=0; i<list.length(); i++)      O(k)
{
  list[i] = -1;
}
while(count > 0)                        O(k+a); where a is an int number
{
  int guess = random(n);                O((k-1)+a)
  boolean found = false;                O((k-1)+a)
  int init = 0;                         O((k-1)+a)
  while(list[init] != -1)               O(k+a)*O(k-1); Here I thing that
  {                                     the worse case happens when the 
    if(list[init] == guess)             array is nearly full, there
      found = true;                     is only one cell left and we
    init++;                             keep search for a unique number.
  }
  if(!found)                            O(1)
  {
    list[init] = guess;
    count--;
  }
}
return list;

В результате я думаю, что общая сложностьэто O (k + a) * O (k-1), где K - количество уникальных элементов, которые мы хотим извлечь из списка, а a - целое число.

Я очень признателен, если бы вы могли помочь мне сэтот вопрос.

...