K
K
kot-airplane2017-08-13 08:53:38
Programming
kot-airplane, 2017-08-13 08:53:38

How to calculate the complexity of an algorithm?

For example, the program analyzes the text and extracts 5 parameters from it, they are added to an array. At the next stage, the list of such arrays is processed, and when processing each one, it is required to find the maximum element, i.e. loop through the array first.
Let's say when creating an array of 5 elements, you can add if and add a value to the beginning or end of the array, so we will spend a little time here, but in the array list they will already be sorted and the maximum element will always be the first element of the array.
In this case, is it possible to mathematically calculate whether the variant will work faster with a pre-sorted array or not, and how to do it? (assume that the execution conditions and the data are exactly the same)

Answer the question

In order to leave comments, you need to log in

2 answer(s)
R
res2001, 2017-08-13
@res2001

Suppose when creating an array of 5 elements, you can add if and add a value to the beginning or end of the array

Well, one IF is not enough here and it is not necessary to add to the beginning or to the end, what are you not considering adding between elements? This is when there is only 1 element in the array - there will be 1 if. But even with one element there is a problem - in what place in the array you place it initially, because you, in general, do not know what elements will be next.
In short - it's about what it will come out. Only if in the variant with subsequent sorting, you have a quick sorting algorithm, then in the variant of a constantly sorted array, it is not known how well you will be able to implement this.
And it is not clear on what YAP you are doing all this.

A
Andryukha, 2017-08-14
@syrov

Let's try, write some pseudocode.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question