IOS often meet questions – algorithm chapter

Q&A

1. Time complexity/space complexity

1. Time complexity

Time frequency

The time consumed by the execution of an algorithm cannot be calculated theoretically, but can only be known by running tests on the machine. But it’s not possible and it’s not necessary to test every algorithm on the machine,

You just need to know which algorithm takes more time and which algorithm takes less time. And the time an algorithm takes is directly proportional to the number of times statements in the algorithm are executed,

Whichever algorithm has more statements executed, 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 basic operations in the algorithm is a function of the 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 not equal to zero, then F (n) is said to be a function of the same order of magnitude as T(n). Denoted as T(n)=O(f(n)), O(f(n)) is called 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, when the time frequency is different, the time complexity may be the same, for example, T(n)=n2+3n+4 and T(n)=4n2+2n+1 have different frequency, but the time complexity is the same, both are O(n2).

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

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

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

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

O(n cubed), called cubed, is a cubic polynomial function of n.

O of logn is called logarithmic, it’s a logarithmic function of n.

O(nlogn) is called an order of magnitude between the linear and square order

O(2 or 2n) is called exponential, and is an order of magnitude greater than the number n exponential.

O(n!) It’s called the factorial level, which is the same order of magnitude as the factorial of n.

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

2. Space complexity

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

2. What are the common sorting algorithms?

The three sorting algorithms of selection sort, bubble sort and insertion sort can be summarized as follows:

Both divide an array into sorted parts and unsorted parts.

Select sort defines the sorted part at the left end, and then selects the smallest element of the unsorted part to swap with the first element of the unsorted part.

Bubble sort defines the sorted part at the right end, and swaps the largest element to the right end as the unsorted part is traversed.

Insert sort defines the sorted part on the left and inserts the first element of the unsorted part element into the appropriate position of the sorted part.

/** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** And the third, and the fourth... The number swap position * the n-1st pass, and finally the ascending (descending) arrangement of the data can be achieved. * */ void selectSort(int *arr, int length) { for (int i = 0; i < length - 1; Int j = I ++) {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 】 : adjacent elements compare in pairs, compare a trip, the maximum value appears at the end * the first trip: compare two adjacent numbers in turn, constantly exchange (decimal place before, large number after) one by one advance, the maximum value finally appears in the NTH element position * the second trip: Compare the two adjacent numbers in turn, continuously swap (before the decimal, after the large number) to advance one by one, the most value finally appears in the n-1st element *...... ... */ void bublleSort(int *arr, int length) {for(int I = 0; i < length - 1; I++) {for(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 search time (without traversing all data) ** Split search principle: * 1> Array must be ordered * 2> Must know min and Max (know the range) * 3> Dynamically calculate the value of mid, extract the corresponding value of mid for comparison * 4> If the corresponding value of mid is greater than the value to be searched, If the value of mid is less than the value to be searched, Int findKey(int *arr, int length, int key) {int min = 0, int arr, int length, int key); 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

3. String reversal

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

4. List inversion (head difference method)

List inversion (head difference method)

• H Declaration file

Struct Node {int data; struct Node *next; }; Struct Node* ReverseList (struct Node* head); @interface ReverseList: NSObject Struct Node* constructList(void); Void printList(struct Node *head); @endCopy the code

• .m implementation file

#import "reverselist. h" @implementation ReverseList struct Node* ReverseList (struct Node* head) { Struct Node *p = head; Struct Node *newH = NULL; // iterate over the list while (p! Struct Node *temp = p->next; P ->next = newH; // Change the new list header to the current node newH = p; // move p pointer p = temp; } // return newH; } struct Node* head = NULL; 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 the current node to a 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

5. How to find the first character that appears only once (Hash lookup)

• H Declaration file

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

• .m implementation file

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

6. How do I find the common parent of two child views?

• H declaration file

#import <Foundation/Foundation.h> #import <UIKit/UIKit.h> @interface CommonSuperFind : NSObject find the common parent of both views - (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++; } // If not equal, end the loop else{break; } } return result; } - (NSArray <UIView *> *)findSuperViews:(UIView *)view {// initialize to the first superview UIView *temp = view.superview; NSMutableArray *result = [NSMutableArray array]; while (temp) { [result addObject:temp]; // Follow the superview pointer up temp = temp.superview; } return result; } @endCopy the code

7. Median in unordered array (quick sorting idea)

• H declaration file

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

• M implementation file

Int findMedian(int a[], int aLen) {int low = 0; #import "medianfind.h" @implementation MedianFind; int high = aLen - 1; int mid = (aLen - 1) / 2; int div = PartSort(a, low, high); while (div ! Div = PartSort(a, low, div-1); 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[low] <= key) { 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

8. Given an array of integers and a target value, find the two numbers in the array and 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