Algorithms For Dummies. John Paul Mueller
Чтение книги онлайн.

Читать онлайн книгу Algorithms For Dummies - John Paul Mueller страница 21

Название: Algorithms For Dummies

Автор: John Paul Mueller

Издательство: John Wiley & Sons Limited

Жанр: Программы

Серия:

isbn: 9781119870005

isbn:

СКАЧАТЬ complexity O(1): The same time, no matter how much input you provide. In the end, it is a constant number of operations, no matter how long the input data is.

       Logarithmic complexity O(log n): The number of operations grows at a slower rate than the input, making the algorithm less efficient with small inputs and more efficient with larger ones. A typical algorithm of this class is the binary search, as described in Chapter 7 on arranging and searching data.

       Linear complexity O(n): Operations grow with the input in a 1:1 ratio. A typical algorithm is iteration, which is when you scan input once and apply an operation to each element of it. Chapter 4 discusses iterations.

       Linearithmic complexity O(n log n): Complexity is a mix between logarithmic and linear complexity. It is typical of some smart algorithms used to order data, such as merge sort, heapsort, and quicksort. Chapter 7 tells you about most of them.

       Quadratic complexity O(n2): Operations grow as a square of the number of inputs. When one iteration is nested inside another iteration, you have quadratic complexity. For instance, you have a list of names and, in order to find the most similar ones, you compare each name against all the other names. Some less efficient ordering algorithms present such complexity: bubble sort, selection sort, and insertion sort.

       Cubic complexity O(n3): Operations grow even faster than quadratic complexity because there are multiple nested iterations. When an algorithm has this order of complexity and processes a modest amount of data (100,000 elements) it may run for years. When you have a number of operations that is a power of the input, it is common to refer to the algorithm as running in polynomial time.

       Exponential complexity O(2n): The algorithm takes twice the number of previous operations for every new element added. When an algorithm has this complexity, even small problems may take forever. Many algorithms doing exhaustive searches have exponential complexity. However, the classic example for this level of complexity is the calculation of Fibonacci numbers (which, being a recursive algorithm, is dealt with in Chapter 4).

       Factorial complexity O(n!): If the input is 100 objects and an operation on a computer takes 10-6 seconds (a reasonable speed for computers today), completing the task will require about 10140 years (an impossible amount of time because the age of the universe is estimated as being 1014 years). A famous factorial complexity problem is the traveling salesman problem, in which a salesman has to find the shortest route for visiting many cities and coming back to the starting city (presented in Chapter 18).

      Working with Google Colab

      IN THIS CHAPTER

      

Considering what Google Colab provides

      

Using Google Colab to perform common development tasks

      

Making applications run in Google Colab

      

Getting help when you need it

      Colaboratory (https://colab.research.google.com/notebooks/welcome.ipynb), or Colab for short, is a Google cloud-based service that lets you write Python code using a notebook-like environment, rather than the usual IDE. (Jupyter Notebook, https://jupyter.org/, provides a similar environment to Colab on the desktop if you don’t have an Internet connection.) You don’t have to install anything on your system to use it. The benefit of this approach is that you can work with code in small pieces and obtain nearly instant results from any work you do. A notebook format also lends itself to output in a report format that works well for presentations and reports. The first section of this chapter helps you work through some Colab basics and understand how Colab differs from a standard IDE (and why this difference has a significant benefit when learning algorithms).

      You can use Colab to perform specific tasks in a cell-oriented paradigm. The next sections of the chapter go through a range of task-related topics that start with the use of notebooks. Of course, you also want to perform other sorts of tasks, such as creating various cell types and using them to create notebooks that have a report-like appearance with functional code.

      Finally, this chapter can’t address every aspect of Colab, so the final section of the chapter serves as a handy resource for locating the most reliable information about Colab.

      

You don’t have to type the source code for this chapter manually. In fact, using the downloadable source is a lot easier. You can find the source for this chapter in the \A4D2E\ A4D2E; 03; Colab Examples.ipynb file of the downloadable source. See the Introduction for details on how to find these source files.

      Colab is designed to mimic a desktop application called Jupyter Notebook (https://jupyter.org/). In fact, it's somewhat difficult to tell the two applications apart in the functionality they provide. Google Colab is the cloud version of Notebook, and the Welcome page makes this fact apparent. It even uses IPython (the previous name for Jupyter) Notebook (.ipynb) files for the site.

      Even though the two applications are similar and they both use .ipynb files, they do have some differences that you need to know about. The previous edition of this book used Jupyter Notebook, but Colab offers the ability to compute anywhere on any device that sports a browser, so this edition of the book focuses on Colab instead. The following sections help you understand the Colab differences.

      Understanding what Google Colab does

      You can use Colab to perform many tasks, but for the purpose of this book, you use it to write and run code, create its associated documentation, and display graphics. The downloadable source for this book is designed to run on Colab, but you can also use it with Jupyter Notebook if you want.