Everyone is welcome to watch my algorithm design and analysis column: Algorithm Design and Analysis_IT Yan’s Blog-CSDN Blog I hope it will be helpful to everyone!
Personal column:
Algorithm design and analysis: Algorithm design and analysis_IT Yan’s blog-CSDN blog
Java Basics: Java Basics_IT Yan’s Blog-CSDN Blog
C language: c language_IT Yan’s blog-CSDN blog
MySQL: Data Structure_IT Yan’s Blog-CSDN Blog
Data structure: Data structure_IT Yan’s blog-CSDN blog
C++: C++_IT Yan’s Blog-CSDN Blog
C51 MCU: C51 MCU (STC89C516)_IT Yan’s Blog-CSDN Blog
Webpage design and application based on HTML5: Webpage design and application based on HTML5_IT Yan’s Blog-CSDN Blog
python: python_IT Yan’s blog-CSDN blog
Welcome to watch, I hope it is useful to everyone!
Table of Contents
Purpose:
content:
Code (C language):
operation result:
Analysis of Algorithms:
Implementation of other programming languages:
Java program:
python program:
C++ program:
Purpose:
1) Understand the idea and basic principles of greedy algorithm;
2) Master the general characteristics of using greedy algorithms to solve problems;
3) Be able to correctly choose greedy strategies for practical problems;
4) Be able to prove the correctness of the algorithm for the selected greedy strategy;
5) Be able to write code correctly according to the greedy strategy;
6) Be able to correctly analyze the time complexity and space complexity of the algorithm.
Content:
Implementing a greedy algorithm for the activity scheduling problem.
Test data is available:
i
1
2
3
4
5
6
7
8
9
10
Begin
1
3
2
5
3
5
6
8
8
2
End
4
5
6
7
8
9
10
11
12
13
Code (C language):
#include <stdio.h>
void activity(int start [],int end[],int n){
int result[n];//result array, stores the selected activity number
int prev_end_time=-1;//The end time of the last selected activity number
int count =0; //Record the number of selected activities
\t
for(int i=0;i<n;i + + ){
int start_time=start[i];
int end_time=end[i];
\t\t
if(start_time >=prev_end_time){
result[count]=i;//Put the activity code into the result array
prev_end_time=end_time;
count + + ;
}
}
printf("The coding sequence of activity arrangements is:");
for(int i=0;i<count;i + + ){
printf("%d ",result[i] + 1);//Note that the activity number starts from 1
}
printf("\\
");
}
int main(){
int start1[]={1,3,2,5,3,5,6,8,8,2};
int end1[]={4,5,6,7,8,9,10,11,12,13};
activity(start1,end1,10);
return 0;
}
Run result:
Algorithm analysis:
When storing n objects,
1. Time complexity analysis:
- A loop is used in the
void activity(int start [],int end[],int n)function, and the number of loops is n.- Constant time is used to perform operations (comparisons, assignments, etc.) inside the loop, and the time complexity is O(1).
- Therefore, the time complexity of the
void activity(int start [],int end[],int n)function is O(n).To sum up: the time complexity of the entire code when storing n objects is O(n).
2. Space complexity analysis:
- The
void activity(int start [],int end[],int n)function defines an integer arrayresult[]of size n, which is used to store the selection activity number. Therefore, the space complexity of this array is O(n).- In addition, several integer variables are also defined in the function, and their space complexity is O(1).
To sum up, the space complexity of the entire code to store n objects is O(n).
It should be noted that the above complexity analysis assumes that the input size is n, which represents the number of activities. If the number of activities is large, the complexity may increase.
Implementation of other programming languages:
Note: The following codes are all generated by AI. If readers find bugs, they can post them in the comment area and we will solve them together!
Java program:
public class ActivitySelection {
public static void activity(int[] start, int[] end, int n) {
int[] result = new int[n]; // Result array, storing the selected activity number
int prevEnd = -1; //The end time of the last selected activity number
int count = 0; // Record the number of selected activities
for (int i = 0; i < n; i + + ) {
int startTime = start[i];
int endTime = end[i];
if (startTime >= prevEnd) {
result[count] = i; //Put the activity code into the result array
prevEnd = endTime;
count + + ;
}
}
System.out.print("The coding sequence of activity arrangements is: ");
for (int i = 0; i < count; i + + ) {
System.out.print((result[i] + 1) + " "); // Note that the activity number starts from 1
}
System.out.println();
}
public static void main(String[] args) {
int[] start = {1, 3, 2, 5, 3, 5, 6, 8, 8, 2};
int[] end = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
int n = 10;
activity(start, end, n);
}
}
It should be noted that the size of arrays cannot be dynamically declared in Java, so in Java code, the size of the array
resultneeds to be determined at the time of definition, which isn. In addition, the loop syntax in Java is different from that in C. You need to usefor,whileordo-whilestatements, etc.
python program:
def activity(start, end, n):
result = [0] * n # Result array, storing the selected activity number
prev_end_time = -1 # The end time of the last selected activity number
count = 0 # Record the number of selected activities
for i in range(n):
start_time = start[i]
end_time = end[i]
if start_time >= prev_end_time:
result[count] = i # Put the activity code into the result array
prev_end_time = end_time
count + = 1
print("The coding sequence of activity arrangements is:", end=' ')
for i in range(count):
print(result[i] + 1, end=' ') # Note that the activity number starts from 1
print()
start1 = [1, 3, 2, 5, 3, 5, 6, 8, 8, 2]
end1 = [4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
activity(start1, end1, 10)
It should be noted that fixed-size arrays cannot be declared directly in Python, so a list can be used instead. In Python, indexing starts at 0, so add 1 to the activity number before printing. In addition, use the
print()function in Python instead of theprintf()function in C language for output.
C++ program:
#include <iostream>
using namespace std;
void activity(int start[], int end[], int n) {
int result[n]; // result array, storing the selected activity number
int prev_end_time = -1; // The end time of the last selected activity number
int count = 0; // Record the number of selected activities
for (int i = 0; i < n; i + + ) {
int start_time = start[i];
int end_time = end[i];
if (start_time >= prev_end_time) {
result[count] = i; //Put the activity code into the result array
prev_end_time = end_time;
count + + ;
}
}
cout << "The coding sequence of activity arrangements is:";
for (int i = 0; i < count; i + + ) {
cout << result[i] + 1 << " "; // Note that the activity number starts from 1
}
cout << endl;
}
int main() {
int start1[] = {1, 3, 2, 5, 3, 5, 6, 8, 8, 2};
int end1[] = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
activity(start1, end1, 10);
return 0;
}
C++ is similar to the C language, but you need to pay attention to issues such as header files, namespaces, and input and output. In this example, we use
as the standard input and output library, and add theusing namespace std;statement so thatcan be omitted in subsequent code std::namespace prefix. When outputting, usecoutandendlinstead of theprintf()and\\symbols in C language. Other parts are similar to C language code.