Help-Improving runtime complexity of the method

In summary: divided by 3 would return 1, 1, 1. {1,1,2,2,2,3} divided by 3 would return 2, 1, 1. {2,2,3,3,3,4} divided by 3 would return 1, 1, 1. {3,3,4,4,4,5} divided by 3 would return 1, 1, 1. {4,4,5,5,5,6} divided by 3 would return 1, 1, 1. {5,5,6,6,6,7} divided by 3 would return 1, 1, 1. {6,6,7,7,7,8} divided by 3 would return 1
  • #1
moshiko
2
0
Hello everyone,
Looking for a more efficient solution to method 'what', in terms of run-time complexity and space.
The method finds the largest cell sequence that the organs sum is divided by 3.(Correct me if I'm wrong)

As it seems runtime complexity here is O(n ^ 3).
I came to solution of O(n ^ 2), is there a more effective solution? Explain please,
Thanks for the helpers !


HrtOq9r.png
NT6Oi4w.jpg
 
Technology news on Phys.org
  • #2
It seems you are resumming things over and over in the f method

f(a,0,3) means sum elements a[0..3]

then you do f(a,0,4) which means sum elements a[0..4]

why not remember the sum and just add a[4] to it?

This will eliminate the innermost loop in the f method.
 
  • #3
As a good rule of thumb, correct algorithms have the potential to contribute the most to efficiency.

If I understand what this code is supposed to do, I would consider a different algorithm - Kadane's maximum subarray algorithm.
https://en.wikipedia.org/wiki/Maximum_subarray_problem
 
  • #4
Hmm - found this in my code store, made simple example in C
Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Kadanes Algorithm  in C
// Parameters:
// a array of integers
// sz number of elements in the array

int max_sum_subarr(int *a, const size_t sz)
{
    int i=0;
    int local_mx = INT_MIN;
    int mx_ending = 0;
    for (i = 0; i < sz; i++)
    {
        mx_ending = mx_ending + a[i];
        if (local_mx < mx_ending)
            local_mx = mx_ending;
        if (mx_ending < 0)
            mx_ending = 0;
    }
    return local_mx;
}
int main(int argc, char **argv)
{
   size_t sz=7;
   int a[7]={1 , 4, -1, -7, 3, 2, 1 };
   
   printf("maximum sub array = %d\n", max_sum_subarr(a, sz) );
   
   return 0;
}

Note the complexity change.
 
  • #5
I need to find algorithm to method that return the size of largest sequence that his amounts divisible by 3, in O N complexity..
for example, for array
{0,0,1,1,1,1,1} the method return 5 . {0,0,1,1,1}
 

Related to Help-Improving runtime complexity of the method

What is runtime complexity and why is it important?

Runtime complexity refers to the amount of time it takes for an algorithm or method to execute. It is important because it directly affects the performance and efficiency of a program. A lower runtime complexity means that the method will execute faster, making the program more efficient.

How can I improve the runtime complexity of my method?

There are several ways to improve the runtime complexity of a method. One approach is to use more efficient algorithms, such as sorting algorithms like merge sort or quicksort. Another approach is to analyze the logic of the method and eliminate unnecessary steps or loops. Additionally, using data structures like hash tables or binary trees can also improve runtime complexity.

What is the difference between time complexity and space complexity?

Time complexity refers to the amount of time it takes for a method to execute, while space complexity refers to the amount of memory or space that is required to run the method. Both are important factors to consider when optimizing the performance of a program.

How do I determine the runtime complexity of a method?

To determine the runtime complexity of a method, you can analyze the number of operations that are performed in the worst-case scenario. This can be done by counting the number of loops, recursive calls, or other operations that are performed based on the input data size. The Big O notation is commonly used to express the runtime complexity of a method.

Are there any trade-offs when trying to improve runtime complexity?

Yes, there can be trade-offs when trying to improve runtime complexity. For example, using more efficient algorithms may require more memory or space, which can affect the space complexity. Additionally, optimizing for runtime complexity may make the code more complex and harder to maintain. It is important to consider these trade-offs and choose the best approach for your specific situation.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
10
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
1
Views
2K
  • Programming and Computer Science
Replies
1
Views
3K
  • Quantum Physics
Replies
2
Views
1K
Replies
13
Views
2K
  • Programming and Computer Science
Replies
4
Views
751
  • Programming and Computer Science
Replies
6
Views
3K
  • Programming and Computer Science
Replies
1
Views
3K
  • Programming and Computer Science
Replies
29
Views
3K
Back
Top