πŸ“š

Β >Β 

⌨️ 

Β >Β 

πŸ“±

3.17 Algorithmic Efficiency

2 min readβ€’january 13, 2023

Minna Chow

Minna Chow

Milo Chang

Milo Chang


AP Computer Science Principles ⌨️

80Β resources
See Units

Problems

Generally speaking, a problem is a task that an algorithm is trying to solve. An instance of the problem is a problem with a specific input. The example the College Board CED gives is that sorting is a problem while sorting the list [2, 3, 1, 7] is an instance of the problem.
Some examples of common problem types are decision problems and optimization problems. Decision problems have a yes/no answer, while optimization problems ask what the best solution is to the task at hand.
Finding out if a number is prime is a decision problem, because you can answer that question with a yes or a no. Finding the shortest path between two cities, on the other hand, is considered an optimization problem. It wants the best answer (in this case the shortest), not just an answer.
https://firebasestorage.googleapis.com/v0/b/fiveable-92889.appspot.com/o/images%2F-Sh0mIlTWmXUS.gif?alt=media&token=502e3e52-249f-4c2a-8ecb-b585adc784b9

It's more optimal for a computer to find the best route than it is for you to attempt it with a map. Image source: Moonrise Kingdom/GIPHY

Efficiency

An algorithm's efficiency is an estimate of how many computational resources (like power, memory or time) it uses. It's officially expressed as a function of the size of the input. This just means that the efficiency varies based on the input sizeβ€”the bigger the input, the more resources it'll use, and vice versa. There are formal equations to calculate it, but you don't have to know them for the AP CSP test.
Informally, efficiency is measured by determining how many times a statement or statement group executes. Algorithms that run with a polynomial efficiency or lower are said to run in a reasonable amount of time while algorithms that run with an exponential or factorial efficiency run in an unreasonable amount of time.
Different correct algorithms for the same problem can have different efficiencies, just like how different ways to solve a problem can take longer or shorter or be more or less effective.
Some problems can't be solved in a reasonable amount of time. In this case, computers turn to an approximate solution. The technique to find this approximate solution is known as a heuristic.
Browse Study Guides By Unit
πŸ•ΉUnit 1 – Creative Development
βš™οΈUnit 2 – Data
πŸ“±Unit 3 – Algorithms & Programming
πŸ–₯Unit 4 – Computer Systems & Networks
⌨️Unit 5 – Impact of Computing
✏️Frequently Asked Questions
πŸ“Exam Prep

Fiveable
Fiveable
Home
Stay Connected

Β© 2023 Fiveable Inc. All rights reserved.


Β© 2023 Fiveable Inc. All rights reserved.