Метод времени/пространства-сложности

Question

У меня возник вопрос, на который мы можем ответить с наилучшей сложностью.

У нас есть один отсортированный массив (int) и значение X. Все, что нам нужно сделать, это найти, сколько мест в массиве равно значению X.

Это мое решение этой ситуации, так как я мало знаю о сложности. Все, что я знаю, что лучше методы не для циклов: считать это команда X

class Question 
{ 
    public static int mount (int [] a, int x) 
    { 
     int first=0, last=a.length-1, count=0, pointer=0; 
     boolean found=false, finish=false; 
     if (x < a[0] || x > a[a.length-1]) 
       return 0; 
     while (! found) **//Searching any place in the array that equals to x value;** 
     { 
      if (a[(first+last)/2] > x) 
       last = (first+last)/2; 
      else if (a[(first+last)/2] < x) 
       first = (first+last)/2; 
      else 
      { 
       pointer = (first+last)/2; 
       count = 1; 
       found = true; break; 
      } 
      if (Math.abs(last-first) == 1) 
      { 
       if (a[first] == x) 
       { 
        pointer = first; 
        count = 1; 
        found = true; 
       } 
       else if (a[last] == x) 
       { 
        pointer = last; 
        count = 1; 
        found = true; 
       } 
       else 
        return 0; 
      } 
      if (first == last) 
      { 
       if (a[first] == x) 
       { 
        pointer = first; 
        count = 1; 
        found = true; 
       } 
       else 
        return 0; 
      } 
     } 
     int backPointer=pointer, forwardPointer=pointer; 
     boolean stop1=false, stop2= false; 
     while (!finish) **//Counting the number of places the X value is near our pointer.** 
     { 
      if (backPointer-1 >= 0) 
       if (a[backPointer-1] == x) 
       { 
        count++; 
        backPointer--; 
       } 
       else 
        stop1 = true; 
      if (forwardPointer+1 <= a.length-1) 
       if (a[forwardPointer+1] == x) 
       { 
        count++; 
        forwardPointer++; 
       } 
       else 
        stop2 = true; 
      if (stop1 && stop2) 
       finish=true; 
     } 
     return count; 
    } 
    public static void main (String [] args) 
    { 
     int [] a = {-25,0,5,11,11,99}; 
     System.out.println(mount(a, 11)); 
    } 
} 

Отпечаток право и печатает «2».

Я просто хочу знать, может ли кто-нибудь подумать о лучшей сложности для этого метода.

Кроме того, как я могу узнать, что такое сложность времени/пространства метода?

Все, что я знаю о сложности времени/пространства, это то, что для цикла O (n). Я не знаю, как вычислить сложность метода.

Большое спасибо!

Редактирование: Это второй в то время как цикл после изменения:

 while (!stop1 || !stop2) //Counting the number of places the X value is near our pointer. 
    { 
     if (!stop1) 
     { 
      if (a[last] == x) 
      { 
       stop1 = true; 
       count += (last-pointer); 
      } 
      else if (a[(last+forwardPointer)/2] == x) 
      { 
       if (last-forwardPointer == 1) 
       { 
        stop1 = true; 
        count += (forwardPointer-pointer); 
       } 
       else 
        forwardPointer = (last + forwardPointer)/2; 
      } 
      else 
       last = ((last + forwardPointer)/2) - 1; 
     } 
     if (!stop2) 
     { 
      if (a[first] == x) 
      { 
       stop2 = true; 
       count += (pointer - first); 
      } 
      else if (a[(first+backPointer)/2] == x) 
      { 
       if (backPointer - first == 1) 
       { 
        stop2 = true; 
        count += (pointer-backPointer); 
       } 
       else 
        backPointer = (first + backPointer)/2; 
      } 
      else 
       first = ((first + backPointer)/2) + 1; 
     } 
    } 

Что вы думаете о смене? Я думаю, что это изменит сложность времени на O (long (n)).

Answer 1

Сначала давайте рассмотрим код:

Код может быть в значительной степени переработан и очищен (который также может привести к более эффективной реализации, но без улучшения времени или пространства сложности), но сам алгоритм довольно хорошо ,

Что он делает, это использовать стандартный бинарный поиск, чтобы найти элемент с требуемым значением, затем сканировать назад и вперед, чтобы найти все другие вхождения значения.

С точки зрения временной сложности, алгоритм O (N). В худшем случае, когда весь массив является одним и тем же значением, и вы завершаете его все на втором этапе (бинарный поиск займет всего 1 итерацию). Космическая сложность O (1). Использование памяти (пробел) не зависит от роста размера ввода.

Вы можете улучшить худшую временную сложность, если вы продолжаете использовать двоичный поиск на 2 под-массивах (назад & спереди) и таким образом увеличивайте «диапазон совпадений» логарифмически. Сложность времени будет O (log (N)). Косвенная сложность останется O (1) по той же причине, что и раньше.

Однако средняя сложность сценария реального мира (где массив содержит различные значения) будет очень близка и может даже склоняться к вашей собственной версии.