How to Decrease Complexity of a Function with Two Loops in Python

Question

This function returns the number of pairs in which A[i] > A[j] for 1 < i < j < n

def calc(A):
    cont = i = j = 0
    while i < len(A):
        j = i + 1
        while j < len(A):
            if A[i] > A[j]:
                cont += 1
            j += 1
        i += 1
    print(cont)

Suppose a list L = [3, 2, 5, 2, 1], then Calc(L) = 7, because 3 > 2, 3 > 2,3 > 1 in the first iteration, 2 > 1, in the second iteration 5 > 2 , 5 > 1 in the third iteration and 2 > 1 in the last iteration. What data structure that is of the division and conquest type would make the above algorithm run faster?

Answer 1

Comparing only 2 to 2 is not possible.

But if it is a "real" algorithm and not something theoretical, you can, within the function itself, go building a list in parallel, this being ordered, and then it is much simpler - because it is possible to do a binary search.

Then you will spend O(log(n)) to build the ordered list, I think the final comparison is O(n log(n))

So, yes, to keep the ordering of the items already seen, and to have a binary search, the coolest is maybe to create a class to do this - in this case we already pulled one of the sleeve here, why create this type of class in Python is very quiet. The standard library implements a heap - which can insert and extract elements in order - but you can’t use binary search in a heap.

My ordered sequence class, however, uses a Python list, with inserts in the middle, to maintain ordering - inserts in the middle of a Python list are relatively costly, although in native code - but in terms of algorithmic complexity are O(N) also - If you want to absorb this cost, then you have to customize the list itself with a linked list data structure - very simple.

If you are going to take this code into some project, I suggest inheriting Sortedseq from abc.collections.MutableSequence - and implement the 3 or 4 more methods that are suggested there - __setitem__, __getitem__, __delitem__, __len__, __insert__ if I’m not mistaken. The special valroes I use in the first line they also look better if they’re a enum.Enum.

MATCH = 0; PREV = -3; POST=-2; NOTFOUND = -1

class SortedSeq:
    def __init__(self, initial=None):
        self.data = []
        if initial:
            for item in initial:
                self.push(item)

    def _find(self, item, start=0, end=None):
        if not self.data:
            return NOTFOUND, 0
        if end == None:
            end = len(self.data)
        if item == self.data[start]:
            return MATCH, start
        if item == self.data[end - 1]:
            return MATCH, end - 1

        middle = (start + end) // 2

        if item == self.data[middle]:
            return MATCH, middle

        if middle == start:
            value = self.data[start]
            return PREV if value < item else POST, start

        if self.data[middle] >= item:
            return self._find(item, start, middle)
        else:
            return self._find(item, middle, end)

    def count_before(item):
        sit, pos = self._find(item)
        if sit in (MATCH, PREV):
            return pos
        return 0


    def find(self, item):
        matched, index = self._find(item)
        if matched == MATCH:
            return index
        return NOTFOUND

    def push(self, item):
        sit, pos = self._find(item)

        if sit == NOTFOUND:
            self.data.append(item)
        elif sit == POST:
            self.data.insert(pos, item)
        else:
            self.data.insert(pos + 1, item)

    def __repr__(self):
        return f"SortedSeq([{self.data}])"

# Disclaimer - não sei se você quer contar 
# os items já vistos que forem iguais ao 
# que está sendo olhado - se não quiser, tem que 
# modificar o "count_before" acima.
def calc(A):
    count = i = j = 0
    seem = SortedSeq()
    for i, item in enumerate(A):
        count += seem.count_before(item)
        seem.push(item)
    return count