Member 13776680 Ответов: 0

Как рассчитать временную сложность моего метода

предыстория вопроса
Здравствуйте, мне нужно рассчитать временную сложность моего метода для школы, и они, к сожалению, не дали мне для этого надлежащих инструментов :(. Я пробовал гуглить, но мне не так удобно делать это в одиночку.

задача
У нас есть 2-мерный массив, который сортируется примерно так:
[41] [42] [43] [44] [45] [46] [47] [48] строка 5
[33] [34] [35] [36] [37] [38] [39] [40] строка 4
[25] [26] [27] [28] [29] [30] [31] [32] строка 3
[17] [18] [19] [20] [21] [22] [23] [24] строка 2
[9] [10] [11] [12] [13] [14] [15] [16] строка 1
[1] [2] [3] [4] [5] [6] [7] [8] строка 0

Мне нужно написать метод, который получит этот массив как param, а также int val от пользователя, и метод должен искать его в массиве за время не более O(n).
Это код, который я написал:

<pre>
int l = 0;
int r = m.length-1;  
        while (l <= r)
        {
            int middle = l + ((r-l)/2);
            if (m[middle][m[middle].length-1] == val)
                return true;
            if (m[middle][m[middle].length-1] < val)
                l = middle + 1;
            else
            {
                if (middle == 0) {
                    r = m[middle].length-1;
                    l = 0;
                    if (binarySearch(m, l, r, middle, val) == 0) return true;   
                }
                if (middle > 0)
                    if (m[middle-1][m[middle-1].length-1] < val) {
                        r = m[middle].length-1;
                        l = 0;
                        if (binarySearch(m, l, r, middle, val) == 0) return true;
                    }
                r = middle - 1;
            }
        }
return false
}

Я начинаю с проверки последнего столбца средней строки массива. Если ценность есть Вэл, то отлично.
Если меньше, то я не буду тратить свое время на прежние ряды.
Если значение больше, я затем проверяю, имеет ли строка перед ним(средний -1) последнее значение столбца, которое меньше val. если да, то это означает, что val может быть только в текущей строке. Поэтому я перехожу ко второму бинарному исследованию.
Существует еще один тест, чтобы проверить, если middle равен 0, который переходит к другому binarySearch. Без него я получаю исключение outOfBounds в моей предыдущей проверке middle-1.

В принципе, у меня есть большой метод BinarySearch, который, если он находит последний столбец, который больше val, использует другой BinarySearch.
Вы бы сказали, что это 2(log n)? n (log n)? Мне трудно позвонить.
Спасибо!

Что я уже пробовал:

Google, youtube, Университетская книга

0 Ответов