Anaylyzing Algorithms Using The "Big-Oh" Notation (Data Structure and Algorithms in Python #1003)

-

Anaylyzing Algorithms Using The "Big-Oh" Notation


 Let us design a python program find_max(s) which takes a sequence of numbers as the parameter and computes the maximum element.


def find_max(s):
    largest = s[0] # assume the first element be the largest
    for e in s: # iterate through the sequence
        if e > largest:
            largest = e
 return largest
Analysis: when find_max is invoked, the initialization before the for loop requires only a constant number of primitive operations, we denote this constant number c'. For each iteration of the loop, it also requires a constant number of primitive operations, and we denote this number c''. For the loop executes n times, so we can say the total number of primitive operations can be written as: c' + c''·n. So by the definition of “Big-Oh” notation, we could say this find_max() algorithm runs in O(n) time.

Comments

New comments are not allowed.

Popular posts from this blog

How to write a slide puzzle game with Python and Pygame (2020 tutorial)

-
Image
Table of Contents Preparation Introduction Import modules and define contants Create the main game screen Creae the data structure of the board Let's draw the tiles The game logic Define the missing functions Preparation In this tutorial, we are gonna use Python 3.8 and Pygame v1.96.  For the installation of Python and Pygame, please follow the documents found on each webiste. Python: https://www.python.org/ Pygame: https://www.pygame.org/ Introduction As you can see from the picture above, we create a board with 15 green tiles and one white tile which represent a empty slot. Our gaol is to place all the 15 green tiles back into its sorted order, namely: A B C D E F G H I J K L  M N O If we click on the tile "F", the tile will slide down south. And if all the tiles are back into their sorted order, you won the game and quit the game. That's pretty much the gist of the game, later you could add other features to the game. Import modules and define contatnts impor
Read more

How to create a memory puzzle game with Python and Pygame (#005)

-
First look at the following code: import time # create Font object text_font = pygame . font . SysFont( 'arial' , 50 ) # create a list that stores two pos that going to compare to each other pos_to_compare_list = [] # create a list that stores all the pos that matched pos_matched = [] # set backgroud color to white while True : for event in pygame . event . get(): if event . type == QUIT: pygame . quit() sys . exit() elif event . type == MOUSEBUTTONDOWN: (x,y) = pygame . mouse . get_pos() pos = check_click(x,y, square_pos) if pos: text_surface = text_font . render(board[pos[ 0 ]][pos[ 1 ]], True , WHITE) if len (pos_to_compare_list) < 2 : if pos not in pos_to_compare_list: pos_to_compare_list . append(pos)
Read more

Introduction to multitasking with Python #001 multithreading (2020 tutorial)

-
Image
1. What is multitasking? So far, we have written so many programs with python. All the instructions inside a program run sequentially one by one. Let's look at an simple example: # multithreading_example01.py # basci program without using threading import time def sing (): for i in range ( 5 ): print ( 'Singing...' ) time . sleep( 1 ) def dance (): for i in range ( 5 ): print ( 'Dancing...' ) time . sleep( 1 ) def main (): # singing a song sing() # dancing dance() if __name__ == '__main__' : main()  After running this program, after ten seconds the program exits. But if we want to dance and sing at the same time intead of doing one after another, what we could do with the code? In python, we could use the threading module and run both sing() and dance functions at the same time. Here is how we can do it: # multithreading_example01.py
Read more