Определение временной и пространственной сложности программы - PullRequest
Новая
       110

Определение временной и пространственной сложности программы

0 голосов
/ 28 апреля 2018

Итак, у меня была проблема с написанием кода для стажировки, и часть ее заключалась в определении пространственно-временной сложности моей программы. Программа была примерно такая. 

while(A){
  int[][] grid;
  // additional variables

 while(B){ //for loop involves iterating through grid
  // additional variables
  for(...) 
    for(....)
 }

  for(...) //for loop involves iterating through grid
    for(....)
}

Итак, я сказал, что программа в целом имеет временную сложность (A N ^ 2 + B N ^ 2), поэтому пришла к выводу, что время амортизации O (N ^ 2).

Что касается сложности пространства, я должен был суммировать пространство чисел, используемое всеми переменными? Предполагая, что каждая переменная является целым числом, и в цикле A есть 3, а в цикле B - два, сложность пространства будет (A * 24 + B * 16)?

1 Ответ

0 голосов
/ 28 апреля 2018

Чтобы избежать ошибок, я склонен использовать такой подход, чтобы вы делали примечание для каждой строки , представляющее, сколько раз оно выполнено (чтобы быть более точным, вы можете включать как в лучшем, так и в худшем случае).

С учетом примера идея может выглядеть следующим образом: 

num_exec   
        | while(A){
A       |   int[][] grid;
A       |   additional variables
        |
        |   while(B){ //for loop involves iterating through grid
AB      |     additional variables
ABN^2   |     for(...) 
        |       for(....)
        |   }
        |
AN^2    |  for(...) //for loop involves iterating through grid
        |    for(....)
        | }

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

image

As for your memory complexity, your intuition is right for an 8-bit integer. However, if we are talking about primitive datatypes, you can simply think of them as constants. Thus, you should be rather concerned about complex datatypes i.e. an array, since it aggregates multiple primitives. To sum up, you take into account data sizes of elements designated to preserve your data.

Consequently, applied on the example:

memory   
        | while(A){
ANk     |   int[][] grid;
A3k     |   additional variables
        |
        |   while(B){ //for loop involves iterating through grid
AB2k    |     additional variables
        |     for(...) 
        |       for(....)
        |   }
        |
        |  for(...) //for loop involves iterating through grid
        |    for(....)
        | }

Supposing the grid size of image, a primitive datatype with size of image and the total number of additional variables to be 3 in the outer loop followed by 2 in the inner one, the total space complexity adds up to:

image

Note, to assume the complexities given above image and image have to be both significantly less than image and independent of it at all.

You may be interested in further explanation of the matter provided on this ссылка . Надеюсь, что это поможет (даже если это только приблизительные данные из-за более грубых деталей, которые вы предоставили) и удачи!

...