How to optimize the time of this code?

Asked

Viewed 96 times

-2

I created the code below to solve the problem Vault, of the 2017 OBI. It works, but in 60% of cases it exceeds the time limit, as I do to optimize it?

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int N, M, pAnt, pAtual, resp[10]={0};
    cin >> N >> M;
    int seq[N];
    for(int i=0;i<N;i++){
        cin >> seq[i];
    }
    cin >> pAnt;
    resp[seq[pAnt-1]]++;
    for(int i=1;i<M;i++){
        cin >> pAtual;
        if(pAnt<pAtual)
            for(int j=0;j<10;j++)
                resp[j]+=count(seq+pAnt, seq+pAtual, j);
        else
            for(int j=0;j<10;j++)
                resp[j]+=count(seq+pAtual-1, seq+pAnt-1, j);
        pAnt = pAtual;
    }
    cout << resp[0] << " " << resp[1] << " " << resp[2] << " " << resp[3] << " " << resp[4] << " ";
    cout << resp[5] << " " << resp[6] << " " << resp[7] << " " << resp[8] << " " << resp[9] << endl;
    return 0;
}
c c++

  • Instead of for each digit you count how many times it occurs in the range it would not be more practical to sweep the range once and increment each occurrence of the digit?

1 answer

1

Creating algorithms is different from creating code, because to create an algorithm and well optimized, you must be a good mathematician and know well the functioning as a whole of computing.

About the Complexity of Time

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the problem input. The time complexity of an algorithm is commonly expressed using notation BIG O, that suppresses multiplicative constants and other terms of lesser order. When expressed in this way, the complexity of time is said to be described asymptotically, i.e., how the size of the input goes to infinity. For example, if the time requested by an algorithm on all inputs of size n is at most 5n³ + 3n, the asymptote of time complexity is O(n³).

About the Processing Time

Measure the time spent by an algorithm:

  • Not a good option
  • Depends on the compiler
  • You may prefer some constructions or optimize better
  • Depends on hardware (GPU vs. CPU, desktop vs. smartphone)

Different entries may have different cost

  • Best case
  • Worst case
  • Average case

OFFICIAL SOURCE: WIKIPEDIA

NOTE:

You can read more on this subject at this link and also to know the best algorithms created in relation to time complexity, access the official source above.

Browser other questions tagged c c++

You are not signed in. Login or sign up in order to post.