IOS Development -10 common algorithmic concepts

1. Time complexity

• Time frequency

  The time it takes for an algorithm to execute cannot be calculated theoretically, but only by running tests on a computer. But we can’t and we don’t need to test every algorithm on the computer, just know which algorithm takes more time and which algorithm takes less time. And the amount of time an algorithm takes is directly proportional to the number of statements executed in the algorithm. Whichever algorithm executes more statements, it takes more time. The number of statements executed in an algorithm is called statement frequency or time frequency. Notes for T (n).

• Time complexity

  In general, the number of repeated execution of basic operations in the algorithm is a function of problem size N, expressed by T(n). If there is some auxiliary function F (n), such that when n approaches infinity, the limit value of T(n) /f(n) is a constant that is not equal to zero, then f(n) is a function of the same order of magnitude of T(n). T(n)=O(f(n)), O(f(n)) is the asymptotic time complexity of the algorithm, or time complexity for short.

• In different algorithms, if the number of statements executed in the algorithm is a constant, the time complexity is O(1). In addition, the time complexity may be the same when the time frequency is not the same. For example, T(n)=n2+3n+4 and T(n)=4n2+2n+1, their frequency is different but the time complexity is the same, which is O(n2).

• In order of magnitude, the common time complexity is:

  O(1) is called constant level, and the time complexity of the algorithm is a constant.

  O(n) is called a linear order, and the time complexity is a linear function of the amount of data n.

  O(n²) is called the square order and is of the same order of magnitude as the quadratic polynomial function of the data volume N.

  O(n³) is called the cubic order, and is a cubic polynomial function of n.

  Order logn is called the logarithmic level, which is a logarithmic function of n.

  O(nlogn) is said to be an order of magnitude between the linear order and the square order

  O(2 n) is called exponential and is on the order of magnitude of the exponential function of the data volume N.

  O(n!) It’s called the factorial level, and it’s the same order of magnitude as the factorial of the data volume n.

  The relationship between them is: O (1) < O (logn) < O (n) < O (nlogn) < O (n squared) < O (n) after < O (2 ⁿ) < O (n!) With the increasing of problem size n, the time complexity above increases, and the execution efficiency of the algorithm becomes lower.

2. Space complexity

• Evaluate the storage space required to execute the program. You can estimate how much your program is using the computer’s memory. It does not include the space occupied by the algorithm program code and the data itself. It is usually represented by the number of bytes of extra space used. Its algorithm is relatively simple, denoted as S(n)=O(f(n)), where n represents the size of the problem.

3. Common sorting algorithms

• Selection sort, bubble sort, insertion sort three sort algorithms can be summarized as follows:

  Both divide the array into sorted and unsorted parts.

  Select sort defines the sorted part on the left, and then selects the smallest element of the unsorted part to be swapped with the first element of the unsorted part.

  Bubble sort defines the sorted part at the right end and performs an exchange during the process of traversing the unsorted part, swapping the largest element to the right end.

  Insertion sort defines the sorted part on the left and inserts the first element of the unsorted part into the appropriate place for the sorted part.

/ * * * "selection" : the most value in between * * trip 1: in the n number found in (large) number of minimum 2 trips to swap places with the first number * : in the remaining find the minimum number n - 1 (large) number of swap places with the second number * repeat operation... The third, the fourth... The number exchange position * n-1 trip, finally can realize the ascending (descending) order of data. * */ void selectSort(int *arr, int length) { for (int i = 0; i < length - 1; For (int j = I + 1; j < length; J++) {/ / times if comparing (arr [I] > arr [j]) {int temp = arr [I]; arr[i] = arr[j]; arr[j] = temp; }}}} /** * [Bubble sort] : Compare the two adjacent elements in pairs, after the comparison, the most value appears at the end * the first time: compare the two adjacent numbers in turn, constantly swap (before the decimal, after the large number put) advance one by one, the most value finally appears at the NTH element position * the second time: Compare the two adjacent numbers in turn, constantly switching (before the decimal number, after the large number) advance one by one, the most value finally appears in the n-1 element position *...... ... */ void bublleSort(int *arr, int length) {for(int I = 0; i < length - 1; For (int j = 0; int j = 0; j < length - i - 1; J++) {/ / times if comparing (arr [j] > arr [j + 1]) {int temp = arr [j]; arr[j] = arr[j+1]; arr[j+1] = temp; }}}} /** * Split search: Optimize the search time (without traversing all the data) ** The principle of split search: * 1> Array must be ordered * 2> Must know min and Max (know range) * 3> Dynamically calculate mid and fetch mid for comparison * 4> If mid is greater than the value we are looking for, So Max is going to be smaller than mid-1 * 5> if mid is less than the value we're looking for, Int int (int *arr, int length, int key) {int min = 0, int (int *arr, int length, int key) {int min = 0, max = length - 1, mid; while (min <= max) { mid = (min + max) / 2; If (key > arr[mid]) {min = mid + 1; } else if (key < arr[mid]) { max = mid - 1; } else { return mid; } } return -1; }Copy the code

4. String inversion

Void char_reverse (char *cha) {// Define header pointer char *begin = cha; Char *end = cha + strlen(cha) -1; while (begin < end) { char temp = *begin; *(begin++) = *end; *(end--) = temp; }}Copy the code

5. List reversal (head difference method)

.h Declaration file

#import <Foundation/Foundation. H > struct Node {int data; struct Node *next; }; @interface ReverseList: NSObject // Struct Node* head; Struct Node* constructList(void); Void printList(struct Node *head); @endCopy the code

M implementation file

#import "reverselist. h" @implementation struct Node* ReverseList (struct Node* head) { Struct Node *p = head; // Struct Node *newH = NULL; While (p! Struct Node *temp = p->next; P ->next = newH; // Change the new list header to the current node newH = p; P = temp; } // Return the inverted list header node return newH; } struct Node* constructList(void) {struct Node* head = NULL; Struct Node *cur = NULL; for (int i = 1; i < 5; i++) { struct Node *node = malloc(sizeof(struct Node)); node->data = i; If (head == NULL) {head = node; } else{cur->next = node; } // Set current node to new node cur = node; } return head; } void printList(struct Node *head) { struct Node* temp = head; while (temp ! = NULL) { printf("node is %d \n", temp->data); temp = temp->next; } } @endCopy the code

6. Merge ordered arrays

.h Declaration file

#import <Foundation/Foundation.h> @interface MergeSortedList : NSObject // mergeList(int a[], int aLen, int b[], int bLen, int result[]); @endCopy the code

M implementation file

#import "MergeSortedList.h" @implementation MergeSortedList void mergeList(int a[], int aLen, int b[], int bLen, int result[]) { int p = 0; Int q = 0; Int I = 0; While (p < aLen &&q < bLen) {if (a[p] <= b[q]) {// Store the value of array A result[i] = a[p]; // move the pointer to p++; } else{result[I] = b[q]; // Move the pointer to array b ++; } // point to the next location to store the merged results i++; } while (p < aLen) {result[I] = a[p++]; i++; } while (q < bLen) {result[I] = b[q++]; i++; } } @endCopy the code

7. Find the first character that occurs only once (Hash lookup)

.h Declaration file

#import <Foundation/Foundation. H > @interface HashFind: NSObject #import <Foundation/Foundation. H > @interface HashFind: NSObject #import <Foundation/Foundation. H > @interface HashFind: NSObject #import <Foundation/Foundation. @endCopy the code

M implementation file

#import "HashFind.h" @implementation HashFind char findFirstChar(char* cha) { char result = '\0'; Int array[256]; // Define an array to store the number of occurrences of each letter. For (int I =0; i<256; i++) { array[i] =0; } // Define a pointer to the current string header char* p = cha; While (*p! = '\ 0') {/ / in the corresponding storage location for occurrences + 1 operation array [* (p++)] + +; } // redirect the P pointer to the string header P = cha; While (*p! If (array[*p] == 1) {result = *p; break; } // iterates backwards to p++; } return result; } @endCopy the code

8. Find the common superview of the two child views

.h Declaration file

#import <Foundation/Foundation.h> #import <UIKit/UIKit.h> @interface CommonSuperFind : NSObject - (NSArray<UIView *> *)findCommonSuperView (UIView *) View other (UIView *)viewOther; @endCopy the code

M implementation file

#import "CommonSuperFind.h" @implementation CommonSuperFind - (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther { NSMutableArray *result = [NSMutableArray array]; NSArray *arrayOne = [self findSuperViews:viewOne]; NSArray *arrayOther = [self findSuperViews:viewOther]; int i = 0; While (I < MIN((int)) arrayone.count, (int) arrayOther. Count)) {/ / reverse way to obtain various views of parent UIView * superOne = [arrayOne objectAtIndex: arrayOne. Count - I - 1]. UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - 1]; If (superOne == superOther) {[result addObject:superOne]; i++; } else{break; } } return result; } - (NSArray <UIView *> *)findSuperViews (UIView *)view {// initialize the first superview UIView *temp = view.superview; NSMutableArray *result = [NSMutableArray array]; while (temp) { [result addObject:temp]; // Select temp = temp. Superview; } return result; } @endCopy the code

9. Median in an unordered array (quicktype idea)

.h Declaration file

#import <Foundation/Foundation. H > @interface MedianFind: NSObject // Int findMedian(int a[], int aLen); @endCopy the code

Int findMedian(int a[], int aLen) {int low = 0; int high = aLen - 1; int mid = (aLen - 1) / 2; int div = PartSort(a, low, high); while (div ! = mid) {if (mid < div) {div = PartSort(a, low, div-1); } else {div = PartSort(a, div + 1, high); } // Return a[mid]; } int PartSort(int a[], int start, int end) { int low = start; int high = end; Int key = a[end]; While (low < high && a[low] <= key) {++low; } while (low < high && a[high] >= key) {--high; } if (low < high) {int temp = a[low]; a[low] = a[high]; a[high] = temp; } } int temp = a[high]; a[high] = a[end]; a[end] = temp; return low; } @endCopy the code

10. Given an array of integers and a target value, find the two numbers in the array that are the target value.

- (void)viewDidLoad {

    [super viewDidLoad];

    NSArray *oriArray = @[@(2),@(3),@(6),@(7),@(22),@(12)];

    BOOL isHaveNums =  [self twoNumSumWithTarget:9 Array:oriArray];

    NSLog(@"%d",isHaveNums);
}

- (BOOL)twoNumSumWithTarget:(int)target Array:(NSArray<NSNumber *> *)array {

    NSMutableArray *finalArray = [NSMutableArray array];

    for (int i = 0; i < array.count; i++) {

        for (int j = i + 1; j < array.count; j++) {

            if ([array[i] intValue] + [array[j] intValue] == target) {

                [finalArray addObject:array[i]];
                [finalArray addObject:array[j]];
                NSLog(@"%@",finalArray);

                return YES;
            }
        }
    }
    return NO;
}
Copy the code

At the end of the article: iOS hot corpus

• 1.BAT and other large factory iOS interview true question + answer Corpus

• 2.A must-see book for iOS Mid and advanced Development

• 3.IOS Development Advanced Interview “resume making” guide

• (4)The iOS interview process to the basics