All geek questions in one place

The complexity of my algorithm is how I can calculate this and further optimize the algorithm?

I developed a recursive algorithm and wrote it in Python. When I measure the runtime with different parameters, it seems to take exponential time. Moreover; it takes more than an hour and a half to end with small numbers such as 50. (I did not wait until it ends, but it seems that it has not finished within a reasonable period of time, suppose it is exponential).

So, I'm curious about the runtime complexity of this algorithm. Can someone help me get the equation T (n, m)? Or figure out big-oh?

The algorithm below:

# parameters:
# search string, the index where we left on the search string, source string, index where we left on the source string,
# and the indexes array, which keeps track of the indexes found for the characters
def find(search, searchIndex, source, sourceIndex, indexes):
    found = None
    if searchIndex < len(search): # if we haven't reached the end of the search string yet
        found = False
        while sourceIndex < len(source): # loop thru the source, from where we left off
            if search[searchIndex] == source[sourceIndex]: # if there is a character match
                # recursively look for the next character of search string 
                # to see if it can be found in the remaining part of the source string
                if find(search, searchIndex + 1, source, sourceIndex + 1, indexes):
                    # we have found it
                    found = True # set found = true
                    # if an index for the character in search string has never been found before.
                    # i.e if this is the first time we are finding a place for that current character
                    if indexes[searchIndex] is None:
                        indexes[searchIndex] = sourceIndex # set the index where a match is found
                    # otherwise, if an index has been set before but it different from what
                    # we are trying to set right now. so that character can be at multiple places.
                    elif indexes[searchIndex] != sourceIndex: 
                        indexes[searchIndex] = -1 # then set it to -1.
            # increment sourceIndex at each iteration so as to look for the remaining part of the source string. 
            sourceIndex = sourceIndex + 1
    return found if found is not None else True

def theCards(N, colors):
    # allcards: a list 1..N of characters where allcards[i] is 'R' if i is a prime number, 'B' otherwise.
    # so in this example where N=7, allcards=['B','R','R','B','R','B','R']
    allcards = ['R' if isPrime(i) else 'B' for i in range(1, N + 1)]
    # indexes is initially None.
    indexes = [None] * len(colors)

    find(colors, 0, allcards, 0, indexes)
    return indexes    

if __name__ == "__main__":
    print theCards(7, list("BBB"))

I don’t know if I need to understand the problem and the algorithm to get the worst working time, but here is the problem I tried to solve:

Problem:

SRC SEA, SEA SRC , SEA SRC. SEA SRC, -1.

; BRRBRBR (N = 7), - BBB: "B" "BBB" 0 . "B" 3 , "B" 5- . ; BBB, , , [0,3,5].

, - BRRBRB (N = 6), - RBR: "R" "RBR" 1 2. 3 "B" 4 "R" . "R" , . , B R, . , [-1,4,5].

, , - [B, R, R, B, R, B, R, 'B', 'B', 'B', 'R', 'B', 'R', 'B', 'B', 'B', 'R', 'B', 'R', 'B ',' B ',' B ',' R ',' B ',' B ',' B ',' B ',' B ',' R ',' B ',' R ',' B ',' B, B, B, B, B, B, 'B', 'R', 'B', 'B', 'B', 'B', 'B', 'R', 'B', 'B', 'B', 'B', ' 'B'] (N = 58)   - RBRRBRBBRBRRBBRRBBBRRBBBRR. [-1, -1, -1, -1, -1, -1, -1, -1, 17, 18, 19, 23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 47, 53], , , = (

:

, "" -1 . (, , ) , . . , .

, , T (n, m), n m - .

, ! =)

EDIT - IVIad:

def find2(search, source):
    indexes = list()
    last = 0
    for ch in search:
        if last >= len(source):
            break
        while last < len(source) and source[last] != ch:
            last = last + 1
        indexes.append(last)
        last = last + 1
    return indexes

def theCards(N, colors):
    # allcards: a list 1..N of characters where allcards[i] is 'R' if i is a prime number, 'B' otherwise.
    allcards = ['R' if isPrime(i) else 'B' for i in range(1, N + 1)]

    indexes = find2(colors, allcards) # find the indexes of the first occurrences of the characters
    colors.reverse() # now reverse both strings
    allcards.reverse()
    # and find the indexes of the first occurrences of the characters, again, but in reversed order
    indexesreversed = find2(colors, allcards)
    indexesreversed.reverse() # reverse back the resulting list of indexes 
    indexesreversed = [len(allcards) - i - 1 for i in indexesreversed] # fix the indices

    # return -1 if the indices are different when strings are reversed
    return [indexes[i] + 1 if indexes[i] == indexesreversed[i] else - 1 for i in range(0, len(indexes))]

if __name__ == "__main__":
    print theCards(495, list("RBRRBRBBRBRRBBRRBBBRRBBBRR"))
+3
3

O(n + m), m - SEA n SRC:

last = 1
for i = 1 to m do
    while SRC[last] != SEA[i]
        ++last

    print last
    ++last (skip this match)

, SEA SRC, , .

; BRRBRBR (N = 7), - BBB

: B SRC: last = 1 print 1, last = 2.

B SRC: last = 4, 4, last = 5.

B SRC: last = 6, 6, last = 7. .

, , , .

, SRC, SEA . while. , while n .

, find(1, 1), ... find(m, n). while . find(i, j) O(m) , while, i = 1 to n. , , , " ", .

, :

i = 1: calls find(2, 2), find(3, 3), ..., find(m, n)
       find(2, 2) calls find(3, 3), ..., find(m, n)
       find(3, 3) calls find(4, 4), ..., find(m, n)
       find(4, 4) calls find(5, 5), ..., find(m, n)
       ...
       total calls: O(m^m)
i = 2: same, but start from find(2, 3).
...
i = n: same

: O(n*m^m). , , .

+4

. , , . , LCS SEA, , SEA SRC, . . http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

+3

Source: https://habr.com/ru/post/1788504/

More articles:


All Articles