Data Structure and Algorithms Using C++. Sachi Nandan Mohanty

Чтение книги онлайн.

СКАЧАТЬ

       Q1. What is the worst-case complexity of the each of the following code fragments?

      Two loops in a row:

       for (i = 0; i < N; i++) { sequence of statements } for (j = 0; j < M; j++) { sequence of statements }

      Answer: The first loop is O(N) and the second loop is O(M). Since you do not know which is bigger, you say this is O(N+M). This can also be written as O(max(N,M)). In the case where the second loop goes to N instead of M the complexity is O(N). You can see this from either expression above. O(N+M) becomes O(2N) and when you drop the constant it is O(N). O(max(N,M)) becomes O(max(N,N)) which is O(N).

       Q2. How would the complexity change if the second loop went to N instead of M?

      A nested loop followed by a non-nested loop:

       for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { sequence of statements } } for (k = 0; k < N; k++) { sequence of statements }

      Answer: The first set of nested loops is O(N²) and the second loop is O(N). This is O(max(N²,N)) which is O(N²).

       Q3. A nested loop in which the number of times the inner loop executes depends on the value of the outer loop index:

       for (i = 0; i < N; i++) { for (j = i; j < N; j++) { sequence of statements } }

      Answer: When i is 0 the inner loop executes N times. When i is 1 the inner loop executes N-1 times. In the last iteration of the outer loop when i is N-1 the inner loop executes 1 time. The number of times the inner loop statements execute is N + N-1 + ... + 2 + 1. This sum is N(N+1)/2 and gives O(N²).

       Q4. For each of the following loops with a method call, determine the overall complexity. As above, assume that method f takes constant time, and that method g takes time linear in the value of its parameter.

      a. for (j = 0; j < N; j++) f(j); b. for (j = 0; j < N; j++) g(j); c. for (j = 0; j < N; j++) g(k);

      Answer: a. Each call to f(j) is O(1). The loop executes N times so it is N x O(1) or O(N).

      b. The first time the loop executes j is 0 and g(0) takes “no operations.” The next time j is 1 and g(1) takes 1 operations. The last time the loop executes j is N-1 and g(N-1) takes N-1 operations. The total work is the sum of the first N-1 numbers and is O(N²).

c. Each time through the loop g(k) takes k operations and the loop executes N times. Since you do not know the relative size of k and N, the overall complexity is O(N x k).

1.8 Questions

      1 What is data structure?

      2 What are the types of operations that can be performed with data structure?

      3 What is asymptotic notation and why is this used?

      4 What is complexity and its type?

      5 Find the complexity of 3n2 + 5n.

      6 Distinguish between linear and non-linear data structure.

      7 Is it necessary is use data structure in every field? Justify your answer.

      Конец ознакомительного фрагмента.

      Текст предоставлен ООО «ЛитРес».

      Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.

      Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.

/9j/4AAQSkZJRgABAQEBLAEsAAD/7SugUGhvdG9zaG9wIDMuMAA4QklNBAQAAAAAAA8cAVoAAxsl RxwCAAACAAAAOEJJTQQlAAAAAAAQzc/6fajHvgkFcHaurwXDTjhCSU0EOgAAAAABIQAAABAAAAAB AAAAAAALcHJpbnRPdXRwdXQAAAAFAAAAAFBzdFNib29sAQAAAABJbnRlZW51bQAAAABJbnRlAAAA AENscm0AAAAPcHJpbnRTaXh0ZWVuQml0Ym9vbAAAAAALcHJpbnRlck5hbWVURVhUAAAAHwBIAFAA IABMAGEAcwBlAHIASgBlAHQAIABQAHIAbwBmAGUAcwBzAGkAbwBuAGEAbAAgAFAAMQAxADAAOAAA AAAAD3ByaW50UHJvb2ZTZXR1cE9iamMAAAAMAFAAcgBvAG8AZgAgAFMAZQB0AHUAcAAAAAAACnBy b29mU2V0dXAAAAABAAAAAEJsdG5lbnVtAAAADGJ1aWx0aW5Qcm9vZgAAAAlwcm9vZkNNWUsAOEJJ TQQ7AAAAAAItAAAAEAAAAAEAAAAAABJwcmludE91dHB1dE9wdGlvbnMAAAAXAAAAAENwdG5ib29s AAAAAABDbGJyYm9vbAAAAAAAUmdzTWJvb2wAAAAAAENybkNib29sAAAAAABDbnRDYm9vbAAAAAAA TGJsc2Jvb2wAAAAAAE5ndHZib29sAAAAAABFbWxEYm9vbAAAAAAASW50cmJvb2wAAAAAAEJja2dP YmpjAAAAAQAAAAAAAFJHQkMAAAADAAAAAFJkICBkb3ViQG/gAAAAAAAAAAAAR3JuIGRvdWJAb+A

СКАЧАТЬ