Java производительность упражнения: 0%

Question

Я сделал этот тест, чтобы бросить вызов себе во время обучения немного Java, и я получил худший результат в тесте производительности, 0%.

Это упражнение:

Вам дается два непустых нуль-индексированные массивы A и B, состоящий из N целых чисел. Эти массивы представляют собой N досок. Точнее, A [K] - это начало и B [K] конец K-й доски.

Далее приведены непустое нуль-индексированный массив С, состоящий из M целых чисел. Этот массив представляет M-гвозди. Точнее, C [I] - это позиция , где вы можете забивать I-й гвоздь.

Мы говорим, что планка (A [K], B [K]) прибита, если существует гвоздь C [I] такой, что A [K] ≤ C [I] ≤ B [K].

Цель состоит в том, чтобы найти минимальное количество гвоздей, которое должно быть использовано , пока все доски не будут прибиты. Другими словами, вы должны найти значение J, чтобы все доски были прибиты гвоздями после использования только первых гвоздей J. Более точно, для каждого элемента настила (А [K], В [K]), такие, что 0 ≤ K < N, должно существовать гвоздь C [I], таких, что я < J и А [К] ≤ С [I], ≤ B [K].

Например, если массивы А, В такие, что:

A[0] = 1 B[0] = 4 
A[1] = 4 B[1] = 5 
A[2] = 5 B[2] = 9 
A[3] = 8 B[3] = 10 four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10]. 

Учитывая массив С, что:

C[0] = 4 
C[1] = 6 
C[2] = 7 
C[3] = 10 
C[4] = 2 if we use the following nails: 

0, то доски [1, 4] и [4, 5] оба будут прибиты. 0, 1, то доски [1, 4], [4, 5] и [5, 9] будут забиты. 0, 1, 2, то доски [1, 4], [4, 5] и [5, 9] будут прибиты. 0, 1, 2, 3, то все плиты будут прибиты гвоздями. Таким образом, четыре - это минимальное количество гвоздей, которые используются последовательно, , позволяя прибивать все доски.

Написать функцию:

класс решение {общественных Int решение (INT [] A, INT [] B, INT [] С); }

, что, учитывая два непустых нуль-индексированные массивы А и В, состоящий из N целые числа и непустое нуль-индексированный массив C, состоящий из М целых чисел, возвращает минимальное количество гвоздей, которые, используемых последовательно , позволяют прибивать все доски.

Если это не возможно, чтобы прибить все доски, функция должна возвращать -1 .

Например, если массивы А, В, С, такие, что:

A[0] = 1 B[0] = 4 
A[1] = 4 B[1] = 5 
A[2] = 5 B[2] = 9 
A[3] = 8 B[3] = 10 

C[0] = 4 
C[1] = 6 
C[2] = 7 
C[3] = 10 
C[4] = 2 the function should return 4, as explained above. 

Предположим, что:

N и М являются целыми числами в диапазоне [1..30,000]; каждый элемент массива A, B, C является целым числом в диапазоне [1..2 * M]; A [K] ≤ B [K]. Сложность:

Ожидаемая наихудшая временная сложность - O ((N + M) * log (M)); Ожидаемый сложность пространства в наихудшем случае - O (M), за пределами хранения ввода (не , считая память, требуемую для входных аргументов). Элементы ввода массивы могут быть изменены.

Вот мое решение:

class Solution { 
    public int solution(int[] A, int[] B, int[] C) { 

     int result = 0; 
     int empties = 0; 

     for(int i = 0; i < C.length; i ++){ 

      for(int j = 0; j < A.length; j ++){ 

       if(A[j] != 0){ 

        if(C[i] >= A[j] && C[i] <= B[j]){ 

         A[j] = B[j] = 0; 
         empties ++; 

        } 
       } 

       if(empties == A.length){ 

        return i + 1; 

       } 
      } 
     } 

     return -1; 
    } 
} 

Это ссылка результата: https://codility.com/demo/results/trainingXXEXMW-KVJ/

Вопросы:

Первый, я не понимаю, почему моя производительность измеренный O ((N + M) * N), а не O (M * N), так как я делаю a для (M) и внутри a for (N). Отказ от ответственности, я узнал только о нотации Big O пару дней назад.

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

Однако я сделал это специально, поскольку ни одна часть упражнения не упоминается, что массивы A и B сортируются так, что 1> = A [K]> = A [K + 1]. И если бы я отсортировал эти массивы, то производительность была бы плохой (я думаю, не знаю, насколько этот вид сильно вредит производительности, просто guesstimate).

Что вы думаете об этом ?.

Answer 1

Я не понимаю, почему моя производительность измеряется O ((N + M) * N), а не O (M * N)

Они, вероятно, делает кривую фитинга против ограниченного числа кривых. (Это проблема с попыткой определить сложность эмпирически.)

И если я отсортирован эти массивы, то производительность будет плохо (я предполагаю, не знаю, сколько-то больно производительность честно, просто догадка).

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