Анализ Big-Oh Notation с вложенными операциями if/вызовы методов

У меня возникла небольшая проблема, полностью захватывающая запись Big-Oh, и пока я видел несколько ответов для операторов If, я ничего не видел с вызовами методов внутри if/else. Я размещаю соответствующий код ниже, линейный и двоичный поиск - это стандартная реализация (я мог бы использовать класс Arrays, но сам решил сам кодировать). Было бы полезно как точное, так и общее обозначение Big Oh. Я сделал попытку ниже.Анализ Big-Oh Notation с вложенными операциями if/вызовы методов

public static int count(int[][] myArray, int query) 
{ 
    queryHits = 0; -----> O(1) 
    queryNumber++; -----> O(1) 
    int subArraymin; -----> O(1) 
    int subArraymax; ----> O(1) 
    int foundIndex = -1; -> O(1) 
    int j = 5000; -----> O(1) 


     for (int i = 0; i<5000; i++)  ------------>O(5000 * O(?) 
     { 
      subArraymin = myArray[0][j];  -------> O(1) 
      subArraymax = myArray[999][j];  ------> O(1) 

      if (query >= subArraymin && query <= subArraymax)  ----> O(1?) 
      { 
       foundIndex = binarySearch(myArray,0 , 1000, query, j); -->O(5000?) * O(log n) 

       if (foundIndex == -1)  --> O(1?) 
       { 
       //irrelevant code omitted 
       } 
       else 
       { 
        linearSearch(myArray, query, foundIndex, j); -----> O(5000?) * O(n) 
       } 
      } 
      else //irrelevant code omitted 
     } 
     return queryHits; 
     }

Мои основные вопросы:
1. Являются ли мои, если заявления O (1) или O (п)? 2. Я считаю, что цикл for for - O (5000 * тело цикла), но так как я называю два разных метода, эти большие методы сначала умножаются?

Благодарим за помощь/указатели!

источник

2015-10-04 Matt R

Нарисуйте блок-схему кода, особенно ветви if и петли. Это очень помогает. В качестве альтернативы, нарисуйте соответствующие линии потока на вашем коде.

В этом случае сложность функций добавляется, а не умножается, поскольку они встречаются в линейной последовательности. Циклы - это то, что многократно, как вы уже отметили в своих «5000 *».

Таким образом, сложность цикла составляет 5000 * (O (log n) + O (n)). Это сводится просто к O (n), так как 5000, 1000 и другие случайные числа - все скалярные константы. Если «5000» происходит от какого-либо другого параметра put (который вы, вероятно, называете «m»), то алгоритм O (m * n).

Насколько это имеет значение для вас до сих пор?

источник

2015-10-04 01:45:56 Prune

Я думаю, что все это имеет смысл на самом деле. 5000 * (большой o тела, в данном случае методы). Хотя я не на 100% на последней части; Я жестко закодировал 5000, поскольку я использую его для обработки 5000 столбцов массива 2d. Так будет ли это O (n) в этом случае? –

Если это массив n * m, то для этого алгоритма вы используете O (n * m). Если массив всегда * не более 5000, то это O (n). Id алгоритм, сделанный для применения к массиву любой ширины (это «m»)? – Prune

Хорошо, тогда это делает! Поэтому, я думаю, теоретически лучше всего было бы устранить линейный поиск и изменить бинарный поиск для выполнения той же работы, поскольку O (n) доминирует над O (log n). Это верно? –

Анализ Big-Oh Notation с вложенными операциями if/вызовы методов

ответ

Смежные вопросы